[Leetcode] Best Time to Buy and Sell Stock I II and III

Problem 

Say you have an array, where the ith element is the price of a given stock on day i.

design an algorithm to find the maximum profit. 

1. If you were only permitted to complete at most one transaction.

2. If you may complete as many transactions as you like

3. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e, you must sell the stock before you buy again).

Algorithms:

Problem 1 is the Maximum Subarray problem, which can be solved using Dynamic Programming. 

Let dp[i] = the maximum sum of subarray ending at i, and the recurrence is 

                    dp[i] =  max(0, A[i], dp[i-1] + A[i]), where i>0, and dp[0] = A[0].    

For ith element, we have three choices, 

1. add nothing, we gain 0 profit

2. add current element, we gain A[i]

3. add current element and previous maximum subarray's sum, we gain dp[i-1] + A[i],

we choose the max of above three options as the max sum end at i. The running time is O(n) and space complicity is O(n). 

We can reduce the space to constant. Observe that when we iterate the array, only the previous dp value is used. In addition, when dp[i-1] < 0, it must be smaller than A[i], therefore, we can safely set it to zero. We can maintain two variables, max_so_far and max_ending_here

For i = 0 to A.length - 1

   max_ending_here += max_ending_here + A[i]

   max_so_far = max(max_so_far, max_ending_here)

   max_ending_here = max(0,max_ending_here)

End

Problem 2 is the Maximum subsequence. Simply accumulate all the positive difference between A[i] and A[i-1].

Problem 3 
One obvious solution to problem 3 is to divide the array into two parts, say left and right. Then the problem is reduced to problem 1, finding the maximum subarray of left and right. The running time is O(n^2), since we divide at n positions (including not divide at all).

The above algorithm used divide, so we may devise a divide-and-conquer algorithm. If we divide the array into two halves, we need to find the solution in the left half and right half. In addition, a maximum subarray may cross the middle point. So, this solution is not easy to implement.

A O(n) solution exists. the original post can be found here.
Following the dynamic programming solution in problem 1, we can use two arrays E and S, where
      E[i] = maximum subarray sum ending at i
      S[i] = maximum subarray sum starting at i
Therefore, the maximum two transitions sum = max(E[i]+S[i])

The code should be refactored. 

Code

                                   

[Leetcode] Balanced Binary Tree

Problem

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Definition

• The depth of a node is the number of edges from the node to the tree's root node.

A root node will have a depth of 0.

• The height of a node is the number of edges on the longest path from the node to a leaf.

A leaf node will have a height of 0.


For each node in the tree
   If !(leftSubTree is balanced && rightSubTree is balanced && abs(leftDepth - rightDepth) <=1)
       return false
   EndIf
EndFor

This algorithm has a O(n*Log(n)) running time, since for each node we need to call two height function, which has a running time O(Log(n)). The algorithm below has a better running time O(n).
If a tree is not balanced, height return -1.
This is a special technique for this problem, since the depth of a tree must be non-negative. Generally, we can create a result class, which has a boolean isBalanced field and a int depth field.

     

Code

[Leetcode] Anagrams

Problem

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. For example, 

Input: {"abc", "bca", "bac", "bbb", "bbca", "abcb"}

Output: {"abc", "bca", "bac", "bbca", "abcb"}, 

since "bbb" does not have an anagram

Algorithm

When check existing, first consider the hash map. We create a hash map, where 

                                 [key, value] = [a sorted string, list of index whose sorted format equals key]. 

After iterate all strings in input, we build a hash map. If a string has at least anagrams in the input, its value should have at least two elements. We can then iterate the keySet of the hash map, add the index list if its length is larger than 1.

Sort a String

Note, there is no String.sort() method, in order to sort a string

char[] c = str.toCharArray();
Arrays.sort(c);
String sorted = new String(c);

Code

[Leetcode] Add Two Numbers

Problem

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Similar to the Add Binary Number
See: http://leetcodewz.blogspot.com/?zx=9c74695cd644c879

Follow up: 

What if the digits are stored not in reverse order, but in sequential order ? For example:

Input: (1 -> 2 -> 3) + (4 -> 5)
Output: 1 -> 6 -> 8

1. We can reverse two lists first, then call above algorithm as a subroutine.
2. Or

Code

[Leetcode] Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).
For example, a = "11" b = "1",  return "100".

Similar to Decimal Addition, using a carry to store the current digit and carry to next digit.
For dth digit
   carry = carry + a[d] + b[d]//if a or b's length < d, just add zero
   c[d] = carry%base
   carry = carry/base
End

If using a string builder, the result is in reverse order.
Note finally the carry may be non zero.

Code:

[Leetcode] TwoSum, ThreeSum, FourSum and KSum

Two Sum:

Given an array of integers A, and a target t,  find two numbers in A such that their sum equals t. Return the index of two numbers, in increasing order. You may assume that each input would have exactly one solution.
Example:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Algorithm:

1. Brute Force: 
Find all pairs of numbers and calculate their sum, if it equals the target return their index in increasing order. Running time = O(n^2).

2. Sort + Double Pointer
First, sort the array in O(n*Log(n)) time. Then use two pointers p and q, p scans from left to right, and q scans from right to left.
While(p < q)
       if(p+q = target) return p and q
       else if(p+q < target) p++
       else q++
End
Therefore, the running time = O(n*Log(n))

3. Hash Map:
We can do even better, by using hash map. First we create a hash map, where
                                    [key, value] = [target - A[i], i].
This requires O(n). Then, we iterate the array. If A[j] contains in map, which means A[j] = target - A[i], we return i and j. This solution has a running time O(n), and its space complicity is O(n). We used O(n) space to reduce the running time.
Note, one number may be used twice, therefore, we need to check j != map.get(A[j])

Three Sum:

Find three numbers, instead of two, where a+b+c = target, return their index in increasing order. 

Algorithm:

1. Reduce to Two Sum 

Sort Array A

For each  i = 0 to A.length-1

        (j,k) = twoSum(A.rest, target - A[i]) 

        If j,k are valid solution 

             return i,j,k

        End

End

Running Time = O(n^2).

2. Hash Map

Create a hash map where [key, value] = [target - A[i], i]

For j = 0 to A.length -2

   For k = j+1 to A.length-1

        if(A[j] + A[k] is in map AND its index > k)

               return j,k and i

End

Running time = O(n^2). 

Here, index > j ensures no duplicate solutions, each newly found solution is a new solution. If For example, A = [1,2,3,4,5] and target = 9. When j = 1, and k =2, we can find a solution index = [1,2,3]. However, if we don't require i > k, we will get this solution again, when j =2 and k =3. 

Duplicate elements. 

How about A has duplicate elements, e.g A = [-1,-1,0,1] and target = 0. I should have only one solution [-1,-1,0]. But using above algorithm, we will get two results. 

Observation :

     for fixed j, once we find a k > i and i > k that A[j]+A[k] + A[i] = target, we will not find any new solution with j and this k. 

Therefore, when we enter the if block, we can safely skip all other same elements equal to A[k]. See more details in code below. 

Four Sum

We can reduce the four sum problem to a three sum problem, then to a two sum problem. 

For i = 0 to A.length-4

   For j = 0 to A.length-3

        find twoSum in A[j+1 to End] and target = -(A[i] + A[j])

   EndFor

EndFor

Also, we need to skip all duplicate solutions. Running time = O(n^3). 

Three Sum Closest

Using hash map is hard to solve this problem, instead we can reduce it to two closet sum problem. 

For each i = 0 to A.length-1

   find a two sum in A[i+1 to end] which is closest to target - A[i]

End