Heap Sort in Java

What is Heap

Reference

www.youtube.com

Heap is the tree structure that has two following restrictions.

1. Binary Tree
2. Parent node is smaller or bigger than children nodes.

Heap is good at controlling the relation about small and large. So heap is used to sort algorithm called Heap Sort and Priority Queue.

Structure Of Heap

Heap class has a array to store some elements. The index of this array express the position of the Binary Tree. The position of the root node is zero. A relation of parent and children is like this.

• Current Node Index: i
• Parent Node Index: (i - 1) / 2
• Left Child Node Index: 2 * i + 1
• Right Child Node Index: 2 * i + 2

Functions

Heap class has two mainly functions, void add(int item) and int poll(). In MinHeap that root node is smallest of all nodes case, these functions are defined like this.

• void add(int item): Insert the item into heap while keeping the above restriction, parent node is smaller or bigger than children nodes.
• int poll(): Remove root node from heap while keeping the restriction.

Heap structure always have to be keep the restriction. So when we insert or remove item from heap, we have to adjust the tree.

Source Code

Bucket Sort in Java

What is Bucket Sort

Bucket Sort is linear sort algorithm. It takes O(N) time. But this algorithm has some restrictions to use.

The restrictions are following

• We know the maximum value in array
• The maximum value is not too large
• each element is Integer .

In Bucket sort, we have to array called bucket that the size is max value in array. So if the max value is too large, we cannot create the array because we would get OutOfMemoryError. And each element in array will be index of array, so each element have to be Integer.

Structure of Bucket Sort

Bucket sort is implemented by using array like this.

1. Prepare a array that the size of array is max value in inputted array
2. Put element into the position of array called bucket where element is index.
3. Take elements from bucket in order.

Complexity

Time complexity is 0(N). This is very fast. Space complexity is O(max value). This is not good point.

Source Code

Maximum Subarray

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

leetcode.com

Solution

By dynamic programming, we can solve this problem in O(N) time.

Make Recurrence Relation

We can define dp(i) following
dp(i) := max(dp(i - 1) + arr[i], arr[i]

This dp(i) means that it is a max value in all subarrays that range is until position i.

Source Code

Find All Anagrams in a String: Amazon

Problem

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter.

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Solution

Naive Solution

The time complexity of naive solution is O(N*M) time. N and N are the length of the input strings s and p. we check all string that starts from each index in s. By repeating M times this handling, we can solve it.

And it is good to user integer of array in order to keep the count of character appearance. In input string is ASCII case, the maximum index will be 256.

Optimize Solution

This algorithm takes O(N) time, so this code is faster than naive solution. By control left and right index like sliding window, we can check all anagrams in O(N) time.

The condition of anagram is the following.

• two strings are same length.
• count of appearance of each character are same.

In above code, if (count == 0) { means that all characters of p are appeared in s. So, we count up the anagram in this condition.

Count Path Sum in Binary Tree

Problem

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

leetcode.com

Solution

By keeping the prefix sum into Hash Map, we can count the number of path that the sum is inputted sum.

I think about below code.

This algorithm takes O(N) time.

Existence of the number(currSum - target) means that if the number remove, we can consider a path from the next node of the number.

Source Code

LRU Cache

Problem

leetcode.com

Solution

This problem can be solved by Double Linked List and HashMap.

Source Code

Find an Element from Sorted Matrix

Problem

Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

Solution

O(N + M) solution

By traversing matrix from upper right to lower left, we can solve this problem in O(N + M) time.

O((log N)²) solution

Searching a 2D Sorted Matrix Part II – LeetCode

As you can see, the run time complexity of this extreme case is O(lg n)2, which turns out to be even less than O(n).