Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

Did this again on 7/4/2016, just to refresh up my mind, still amazed at how the program is come up with, has an array called dp to cache the result, also, note the array in the for loop starts from 2, since we have defined dp[0] = dp[1] = 1 already, and they don’t conform to the following formula.

Most highly upvoted posts have this solution, basically, the idea is:

Take n = 5 as an example, we can figure out the number of unique binary search trees as follow, we will use an array dp[] of length n+1 to hold the cached calculation:

  1. if we set 1 as root, then there could be null number of BST as its left subtree, and there could be X number of unique BST as its right subtree formed by {2,3,4,5}, and one key point is that the X number of unique BST formed by {2,3,4,5} is exactly the same of that formed by {1,2,3,4}, thus, we could save duplicate calculation and use cached results. (This is Dynamic Programming):
    • So, the total possibilities of using 1 as root, is its left subtree possibilities times its right subtree possibilities.
    • we mark this as: dp[0]*dp[4]
  2. then we continue to set 2 as root, then there could be 1 subtree on its left side, and there could be X number of unique BST on its right formed by {3,4,5}, which is the same number as that formed by {1,2,3}
    • we mark this as: dp[1]*dp[3]
  3. then we continue to set 3 as root, {1,2} will be able to form its left subtree, {4,5} will be able to form its right subtree
    • we mark this as: dp[2]*dp[2]
  4. then, we continue to set 4 as root, {1,2,3} will be able to form its left subtree, {5} will be able to form its right subtree, total possible unique BST using 4 as root will be:
    • dp[3]*dp[1]
  5. finally, we set 5 (n=5 in this example) as root, there will be NO right subtree, {1,2,3,4} will be able to form its left subtree, total possible unique BST using 5 as root will be:
    • dp[4][0]

So, we figured out the pattern/algorithm to calculate the total number of possible unique BST given n is:

dp[n] = dp[0]*dp[n-1] //means we set 1 as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

+ dp[1]*dp[n-2]//means we set as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

+…

dp[n-1]*dp[0]//means we set n as root, the possible unique BSTs on its left side times the possible unique BSTs on its right side

so, it’s like this: dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + ….+ dp[n-2][1] + dp[n-1][0];

Now, it’s time to put it into runnable code, some key notes when converting the above idea into working code:

  1. remember in the problem statement, it says from 1…n, it rules out 0 as a possible value for treenode, so, in order to correctly calculate the result for n, we need to have an array length of n+1, instead of n.
  2. use a nested for loop to implement this (from looking at the pattern of the indices)
  3. we hardcode dp[0] = dp[1] = 1;
  4. remember that all array elements are initialized to be 0, so when we first hit dp[2], it’ll be dp[2] = 0, don’t feel confused that where the initial value of dp[2] will come from
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[i-j]*dp[j-1];
}
}
return dp[n];
}

Advertisements

Sum of Two Integers

https://leetcode.com/problems/sum-of-two-integers/

I’ve shared my thoughts on discuss: https://leetcode.com/discuss/111784/one-liner-with-detailed-explanation

Duplicate it here as well:

The chosen answer from this post: http://stackoverflow.com/questions/9070937/adding-two-numbers-without-operator-clarification helps me understand how it works, and recursion proves to be more intuitive to me than iterative. Basically, with key points:

exclusive or (^) handles these cases: 1+0 and 0+1
AND (&) handles this case: 1+1, where carry occurs, in this case, we’ll have to shift carry to the left, why? Think about this example: 001 + 101 = 110 (binary format), the least significant digits of the two operands are both ‘1’, thus trigger a carry = 1, with this carry, their least significant digits: 1+1 = 0, thus we need to shift the carry to the left by 1 bit in order to get their correct sum: 2


public int getSum(int a, int b) {
if(b == 0) return a;
int carry = (a & b) << 1;
int sum = a ^ b;
return getSum(sum, carry);
}

Or, the above code could be shortened to below:


public int getSum(int a, int b) {
return b == 0 ? a : getSum(a^b, (a&b)<<1);
}

Merge Sort

How to analyze the time complexity for Merge Sort?

  • This video helps a lot: https://www.youtube.com/watch?v=0nlPxaC2lTw
  • Prereq: how to understand O(n), O(logn) etc.
    • say the input size is n, then for a loop that starts from 0 and iterates until n or n-1, we say the time complexity for such a loop is O(n)
      • this is also why, we say the time complexity for binary search is O(logn)
        • i.e. in binary search, we only need to search logn times before we find the target because each time, we cut the size of the input by half, e.g. with an input of size 16, we only need to cut 4 times or less before we could find the target, thus, it’s log16 = 4
      • this is also why, we say the time complexity for insertion sort is O(n2)
        • i.e. insertion sort has two for loops, each for loop has to iterate n times, thus, in total, it will have to loop through n*n, i.e. O(n2) time complexity
  • Then based on the code below, merge sort time complexity could be analyzed as below:
    • we use T(n) to denote the total running time for merge sort to work on an array of size n
    • then sort(arr, l, m) takes T(n/2) time since it’s the half size of the original size
    • similarly, sort(arr, m+1, r) also takes T(n/2) time
    • but merge(arr, l, m, r) will take c*n time (c as a constant) since we’ll have to go through the entire array
    • then T(n) could be represented as T(n) = 2*T(n/2) + c*n (function 1)
    • apparently, this is a recursive function, from it, we could get the following:
      • T(n/2) = 2*T(n/4) + c*n
      • T(n/4) = 2*T(n/8) + c*n
      • T(n/8) = 2*T(n/16) + c*n
      • …..
      • take those into the function 1 and simplify it, we could get: T(n) = 2kT(n/2k)+ k*c*n (function 2)
      • we want to deduce this to T(1) because that is what we know: constant time.
      • in that case, n/2k will be equal to 1 , then we could get n = 2k, then we use log on both sides of the equation, we could get logn = log2k = k (function 3)
      • we take function 3 into function 2, we could get T(n) = 2lognT(1)+ logn*c*n, then using Big O notation (lower-order and constant operations could be neglected), this could be represented as T(n) = O(logn*n) = O(n*logn), i.e. the so-called O(nlogn) time complexity for MergeSort.

Merge Sort is a stable sorting algorithm: the order of equal keys in the original input is respected.

Merge Sort is NOT an in-place algorithm: the amount of extra space needed for merge sort is proportional to the size of the input array, this is different from other sorting algorithms like insertion sort or bubble sort which requires only a temp variable to do swap. However, in merge sort, we divide the arrays into two sub-arrays and we make copy of the entire two sub-arrays. Thus, the extra memory required for doing merge sort is proportional to the size of the input array. We say the space complexity of merge sort is O(n) which means its extra memory required is proportional to the size of the input array.

Merge sort works like this:

It partitions the original array into the most atomic elements, then compare and combine them, thus the code looks like the following:


public static void main(String... args){

int[] a = new int[]{4,3,9,8,7};

MergeSort test = new MergeSort();
test.sort(a, 0, a.length-1);

}

public void sort(int[] arr, int l, int r){
if(l &amp;amp;amp;amp;lt; r){
int m = (l+r)/2;
sort(arr, l, m);
sort(arr, m+1, r);
merge(arr, l, m, r);
}
}

private void merge(int[] arr, int l, int m, int r) {
//find sizes of two subarrays that are to be merged
int size1 = m-l+1;
int size2 = r-m;

//copy the two subarrays into two temp arrays
int[] tempL = new int[size1];
int[] tempR = new int[size2];
for(int i = 0; i &amp;amp;amp;amp;lt; size1; i++){
tempL[i] = arr[l+i];
}
for(int i = 0; i &amp;amp;amp;amp;lt; size2; i++){
tempR[i] = arr[m+i+1];
}

//now we merge the two subarrays

//initial indices of the two subarrays
int i = 0, j = 0;

//initial index of the merged subarray array
int k = l;

while(i &amp;amp;amp;amp;lt; size1 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; j &amp;amp;amp;amp;lt; size2){
if(tempL[i] &amp;amp;amp;amp;lt;= tempR[j]){
arr[k] = tempL[i];
i++;
} else {
arr[k] = tempR[j];
j++;
}
k++;
}

//copy remaining list into arr if any
while(i &amp;amp;amp;amp;lt; size1){
arr[k++] = tempL[i++];
}
while(j &amp;amp;amp;amp;lt; size2){
arr[k++] = tempR[j++];
}
}

A sample walkthrough of the code (omitted merge() function), recursion is so cool/powerful!

MergeSort

Plus One Linked List

https://leetcode.com/problems/plus-one-linked-list/

My own original solution:

public ListNode plusOne(ListNode head) {

//get the length of the list and take out the value of each node and store them into an array
ListNode temp = head;
int len = 0;
while(temp != null){
len++;
temp = temp.next;
}

int[] nums = new int[len];
temp = head;
int j = 0;
while(temp != null){
nums[j++] = temp.val;
temp = temp.next;
}

//plus one into this array: nums
for(int i = len-1; i >= 0; i--){
if(nums[i] != 9){
nums[i]++;
break;
} else {
nums[i] = 0;
}
}

//still assuming the first value in the list should not be zero as it's representing a valid number, although it's in a list
ListNode pre = new ListNode(-1);
if(nums[0] == 0){
//in this case, let's just construct a new linked list and return: only first node value is 1, all the rest is 0
ListNode newHead = new ListNode(1);
ListNode result = newHead;
int count = 0;
while(count++ < len){
newHead.next = new ListNode(0);
newHead = newHead.next;
}
return result;

} else {
pre.next = head;
for(int i = 0; i < len; i++){
head.val = nums[i];
head = head.next;
}
return pre.next;
}
}

 

O(logn) and Binary Search

Tonight, I had a good discussion with Eason, actually Eason enlightened me that:

Binary search is O(logn), imagine an array of size 8, we need to divide it 3 times to find the target in the worst case, which is (log2(8)) = 3. Similarly, given an array of size 16, we need to divide (log2(16)) = 4 times to get the target element.

 

This left me a very deep impression of what O(logn) time is.