Tuesday, July 7, 2015

Triangle | Leetcode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

---

Solution: Allocate two arrays to hold the intermediate results. Initialize an array by copying the values from the last row of the triangle. Loop from the second last row of the triangle to the top. In each iteration, compute the minimum path sum of the next top row, and then swap the two arrays for next reuse. When done, the answer is stored as the first element of the current array.
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0) return 0;
        if (triangle.size() == 1) return triangle.get(0).get(0);

        // Init two arrays to store computation results.
        List<Integer> lastRow = triangle.get(triangle.size() - 1);
        int maxSize = lastRow.size();
        int[] a = new int[maxSize];
        int[] b = new int[maxSize - 1];
        for (int i = 0; i < maxSize; i++) {
            a[i] = lastRow.get(i);
        }

        // Go from bottom-up and calculate minimum along the way.
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> curRow = triangle.get(i);
            for (int j = 0; j < curRow.size(); j++) {
                b[j] = Math.min(a[j], a[j + 1]) + curRow.get(j);
            }
            
            // Swap a and b.
            int[] temp = a;
            a = b;
            b = temp;
        }
        
        return a[0];
    }
}

Sunday, July 5, 2015

Pascal's Triangle II | Leetcode

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

---

Solution: Edit the same array in-place. For index i, since we are going to use indexes i-1 and i to update index i, we need to save the pre-modified value at index i to calculate the next value.
public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        for (int i = 0; i < rowIndex; i++) {
            int last = list.get(0);
            for (int j = 1; j < list.size(); j++) {
                int temp = list.get(j);
                list.set(j, last + list.get(j));
                last = temp;
            }
            list.add(1);
        }
        return list;
    }
}

Pascal's Triangle | Leetcode

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
---

Solution: Start off with the base case, with the first list having only one element "1". For each additional list, put a "1" at the beginning and another "1" at the end. For each element in the middle, add the two adjacent elements from the list at the top to get the element's value.
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();
        if (numRows == 0) return answer;
        answer.add(Arrays.asList(1));
        for (int i = 1; i < numRows; i++) {
            List<Integer> lastList = answer.get(i - 1);
            List<Integer> curList = new ArrayList<>();
            answer.add(curList);
            curList.add(1);
            for (int j = 0; j < lastList.size() - 1; j++) {
                curList.add(lastList.get(j) + lastList.get(j + 1));
            }
            curList.add(1);
        }
        return answer;
    }
}

Populating Next Right Pointers in Each Node II | Leetcode

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:
  • You may only use constant extra space.

For example,

Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL
---

Solution: The trick is to use the linked list of a level to fill up the next lower level. Maintain the first node (curFirst) of the linked list. At the beginning of each loop, set the current node (curNode) to the first node. Then for each left and right children, link them up as you traverse the level from left to right. For the first non-null child node you find, set it to be the first node.
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode curFirst = root;
        TreeLinkNode curNode;
        TreeLinkNode nextNode;
        
        while (curFirst != null) {
            curNode = curFirst;
            curFirst = null;
            nextNode = null;
            
            do {
                if (curNode.left != null) {
                    if (nextNode == null) {
                        nextNode = curNode.left;
                        if (curFirst == null) curFirst = nextNode;
                    } else {
                        nextNode = nextNode.next = curNode.left;
                    }
                }
                
                if (curNode.right != null) {
                    if (nextNode == null) {
                        nextNode = curNode.right;
                        if (curFirst == null) curFirst = nextNode;
                    } else {
                        nextNode = nextNode.next = curNode.right;
                    }
                }
                
                curNode = curNode.next;
            } while (curNode != null);
        }
    }
}

Saturday, July 4, 2015

Populating Next Right Pointers in Each Node | Leetcode

Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
---

Solution: Terminate the linked list of the root node first. Maintain two queues, first queue (curLevel) is the current level of the tree, second queue (nextLevel) is the next level of the tree. For each level, maintain a previous node (prevNode). Link the previous node to the current node. When you are done iterating through the entire tree, the linking is done.
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        root.next = null;
        
        // Iterate through each level of the tree.
        Queue<TreeLinkNode> curLevel = new LinkedList<>();
        Queue<TreeLinkNode> nextLevel = new LinkedList<>();
        
        if (root.left != null) curLevel.add(root.left);
        if (root.right != null) curLevel.add(root.right);
        
        while (!curLevel.isEmpty()) {
            TreeLinkNode prevNode = null;
            do {
                TreeLinkNode curNode = curLevel.remove();
                if (curNode.left != null) nextLevel.add(curNode.left);
                if (curNode.right != null) nextLevel.add(curNode.right);
                if (prevNode != null) prevNode.next = curNode;
                prevNode = curNode;
            } while (!curLevel.isEmpty());
            
            // Terminate the current level linked list.
            if (prevNode != null) prevNode.next = null;
            
            // Swap the curLevel and nextLevel queues.
            Queue<TreeLinkNode> temp = curLevel;
            curLevel = nextLevel;
            nextLevel = temp;
        }
    }
}

Distinct Subsequences | Leetcode

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"
 
Return 3.

---

Solution: I probably felt fortunate that I didn't try to crack my head trying to come up with my own solution. This is a non-trivial 2D dynamic programming problem. If you use brute force, it will not pass large tests in leetcode.

Good detailed explanation can be found in stackoverflow: http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation
public class Solution {
    public int numDistinct(String s, String t) {
        int[] f = new int[t.length() + 1];
        f[t.length()] = 1;

        for (int si = s.length() - 1; si >= 0; si--) {
            for (int ti = 0; ti < t.length(); ti++) {
                if (s.charAt(si) == t.charAt(ti)) {
                    f[ti] += f[ti + 1];
                }
            }
        }
        
        return f[0];
    }
}

Thursday, July 2, 2015

Flatten Binary Tree to Linked List | Leetcode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
 
Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

---

Solution: Use divide-and-conquer to handle the left and right child separately. For each node N, put the left subtree under the right child, set the left child to null, and put the right subtree under the last node of the tree consisting of N and the left subtree of N. This will give you the answer.

We are basically not using the hint of pre-order traversal in any way.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        flattenTree(root);
    }
    
    private TreeNode flattenTree(TreeNode node) {
        if (node == null) return null;
        
        // Flatten right and left tree separately.
        TreeNode right = flattenTree(node.right);
        TreeNode left = flattenTree(node.left);
        
        // Put left subtree under right child.
        node.right = left;
        
        // Left child will always be null.
        node.left = null;
        
        // Find last node of the left subtree including node.
        TreeNode temp = node;
        while (temp.right != null) temp = temp.right;
        
        // Append right subtree to the end of the left subtree.
        temp.right = right;
        
        return node;
    }
}