Leetcode: Populating Next Right Pointers in Each Node

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

Understand the problem:
The problem asks for populating each of node's next pointer to its next right node. If there is no next node, its next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note that you are required to only use constant extra space. 

A native approach:
A very straight-forward solution is to use BFS, where we traverse the tree in level-order. However, this solution requires using a queue, which needs to take extra space. 

A better approach:
For a better approach without using extra space, we can observe the tree structure. Note that for each problem the tree in a perfect binary tree, which means that each node must have its left and right children. It indicates that all nodes except for the last node in each level has its next right node. So for each node has left child, root.left -> root.right; For each node root.right != null && root.next != null , root.right.next = root.next.left.

Code (Java):

/**
 * 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;
        }
        
        if (root.left != null) {
            root.left.next = root.right;
        }
        
        if (root.next != null && root.next.left != null) {
            root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
    }
}

Summary:
This problem is very tricky but if figure out the process of connecting nodes, it becomes very simple.

Update on 2/8/16:
Constant space solution:

/**
 * 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;
        }
        
        TreeLinkNode curr = root;
        
        while (curr != null && curr.left != null && curr.right != null) {
            TreeLinkNode p = curr;
            while (p != null) {
                if (p.left != null) {
                    p.left.next = p.right;
                }
            
                if (p.right != null && p.next != null) {
                    p.right.next = p.next.left;
                }
                
                p = p.next;
            }
            
            curr = curr.left;
        }
    }
}

Leetcode: Pascal's Triangle II

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?

Understand the problem:
The problem is an extension of the Pascal's Triangle I. The mainly difference is it only asks you output the kth row of the triangle. Note that k starts from 0. 

One straight-forward solution is  to generate all rows of the Pascal's triangle until the kth row. In this way the complexity is O(k^2). However the problem asks for using only O(k) extra space. 

Solution:
Note that in the previous solution for Problem I, we only need to results for current and its previous row. That means we only need to maintain these two rows, where the space complexity is still O(k).

Code (Java):

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = new ArrayList<Integer>();
        prev.add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            List<Integer> result = new ArrayList<Integer>();
            result.add(1);
            for (int j = 1; j <= i - 1; j++) {
                result.add(prev.get(j) + prev.get(j - 1));
            }
            result.add(1);
            
            for (int k = 0; k < prev.size(); k++) {
                prev.set(k, result.get(k));
            }
            prev.add(1);
        }
        
        return prev;
    }
}

Discussion:
For the solution above, it takes O(k) space but takes O(n^3) time because the copy of array operations. We need to think of a better solution.

A better solution:
Note that for a[j] = a[j] + a[j - 1], so for each a[j] we can update a[j] from the last a[j] and a[j - 1]. However, if we don't store the previous result, the updated value will pollute the later on numbers. So one solution is to update each number in the row from end in a backward order.

Code (Java):

public class Solution {
    public List getRow(int rowIndex) {
        List result = new ArrayList();
        result.add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            result.add(1);
            for (int j = i - 1; j > 0; j--) {
                result.set(j, result.get(j) + result.get(j - 1));
            }
        }
        
        return result;
    }
}

Leetcode: Pascal's Triangle

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]
]

Understand the problem:
The crux of the problem is to understand what is the "Pascal's triangle"?


As is shown in the figure above, each number in the triangle is the sum of the two directory above it. So we can use this property to generate the result.

Solution:

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (numRows <= 0) {
            return result;
        }
        
        List<Integer> temp = new ArrayList<Integer>();
        temp.add(1);
        result.add(temp);
        
        if (numRows == 1) {
            return result;
        }
        
        for (int i = 2; i <= numRows; i++) {
            List<Integer> curRow = new ArrayList<Integer>();
            curRow.add(1);
            for (int j = 1; j < i - 1; j++) {
                curRow.add(result.get(result.size() - 1).get(j - 1) + result.get(result.size() - 1).get(j));
            }
            curRow.add(1);
            result.add(curRow);
        }
        
        return result;
    }
}

Leetcode: Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Understand the problem:
The problem gives a string containing only digits, restore by returning all possible valid IP addresses combinations. 

So the crux of the problem is to understand "what is a valid IP address"? A valid IP address has the format of xxx.xxx.xxx.xxx, where xxx is a number from 0 to 255. Note that there are some reserved IP addresses, but this problem only asks for the valid structure of the IP addresses. Therefore a valid IP address could range from 0.0.0.0 to 255.255.255.255. 

Recursive Solution:
This is another permutation and combination problem. 

Code (Java):

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<String>();
        
        if (s == null || s.length() < 4) {
            return result;
        }
        
        restoreHelper(s, 0, 1, "", result);
        
        return result;
    }
    
    private void restoreHelper(String s, int start, int segment, String curr, List<String> result) {
        if (start >= s.length()) {
            return;
        }
        
        if (segment == 4) {
            if (isValid(s.substring(start))) {
                result.add(curr + "." + s.substring(start));
            }
            return;
        }
        
        for (int i = 1; i < 4 && start + i < s.length(); i++) {
            String temp = s.substring(start, start + i);
            if (isValid(temp)) {
                if (segment == 1) {
                    restoreHelper(s, start + i, segment + 1, temp, result);
                } else {
                    restoreHelper(s, start + i, segment + 1, curr + "." + temp, result);
                }
            }
        }
    }
    
    private boolean isValid(String str) {
        if (str == null || str.length() > 3) {
            return false;
        }
        
        int num = Integer.parseInt(str);
        if (str.charAt(0) == '0' && str.length() > 1) {
            return false;
        }
        
        if (num >= 0 && num <= 255) {
            return true;
        }
        
        return false;
    }
}

Leetcode: Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Understand the problem:
The problem gives three strings s1, s2, and s3, find out whether s3 is formed by the interleaving of s1 and s2. The crux of the problem is to understand the "interleaving". Basically, we can understand the problem by s2 is formed by connecting s1 and s2 together. The way of connecting could be interleaved. 

DP Solution:
We can use DP to solve this problem. So the steps are:

• Define boolean dp[str1.length() + 1][str2.length() + 1], where dp[ i ][ j ] : means whether str1.charAt(0) to str1.charAt(i) and str2.charAt(0) to str2.charAt(j) could construct the string str3, from 0 to i + j. 
• Transit function: 
• dp[i][j]  = str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] || 
• str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]
• Initial State 
• dp[0][0] = true;
• dp[0][j] = str3.charAt(j) == str2.charAt(j)
• dp[i][0] = str3.charAt(i) == str1.charAt(i)
• Final state dp[str1.length()][str2.length()]. 

Code (Java):

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        
        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) {
            return true;
        }
        
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= s2.length(); i++) {
            if (s2.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[0][i] = true;
            } else break;
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                dp[i][0] = true;
            } else break;
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s3.charAt(i + j - 1) == s1.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j];
                }
                
                if (s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i][j] || dp[i][j - 1];
                }
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}

Leetcode: Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:
The main difference between the BST I is it requires to output all unique BSTs. So we can use recursion solution.


Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTreesHelper(1, n);
    }
    
    private List<TreeNode> generateTreesHelper(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        
        if (start > end) {
            result.add(null);
            return result;
        }
        
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = generateTreesHelper(start, i - 1);
            List<TreeNode> right = generateTreesHelper(i + 1, end);
            
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        
        return result;
    }
}

Leetcode: Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,

Given n = 3, there are a total of 5 unique BST's. 

 1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Understand the problem:
The problem gives an integer n, asks for how many structurally unique BSTs that stores value 1 .. n available? 

Solution:
We use DP to solve this problem:
1. Definition: dp[i] means for integer i, how many unique BST's available.
2. Transit Function: dp[i]

For n = 2, dp[2] = dp[0] * dp[1]  // 1 as root 
                          + dp[1] * dp[0] // 2 as root

For n = 3, dp[3] =  dp[0] * dp[2]            // 1 as root
                          +  dp[1] * dp[1]           // 2 as root
                          +  dp[2] * dp[0]           // 3 as root

dp[i] = sum of dp[k] * dp[i - k - 1]; 0 <= k < i

3. Initial state dp[0] = 1; // Mean empty
                      dp[1] = 1; // 1 as root
4. Final state dp[n]

Code (Java):

public class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        
        return dp[n];
    }
}

A Recursive Approach:

public class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        return numTreesHelper(1, n);
    }
    
    private int numTreesHelper(int start, int end) {
        if (start >= end) {
            return 1;
        }
        
        int totalSum = 0;
        for (int i = start; i <= end; i++) {
            totalSum += numTreesHelper(start, i - 1) * numTreesHelper(i + 1, end);
        }
        
        return totalSum;
    }
}

Summary:
The take-away message for DP problem is the four steps approach. 
1. Define a DP array or matrix.
2. Figure out the transit functions.
3. Handle the initial state
4. Figure out the final state

Leetcode: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Understand of the problem:
The problem asks for outputting all Gray Code. For the background knowledge about the gray code, please refer the link 
http://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81#.E4.BA.8C.E9.80.B2.E4.BD.8D.E6.95.B8.E8.BD.89.E6.A0.BC.E9.9B.B7.E7.A2.BC

For n = 1's Gray Code:
0
---
1

For n = 2 Gray Code:
00
01
-----
11
10

For n = 3 Gray Code:
000
001
011
010
----------
110
111
101
100

So we can see that for the Gray code sequence with n, it equals to (n - 1)'s Gray code sequence, as shown in the upper half the examples. The below halves are equal to the sum of n- 1 gray code plus the 1 << (n - 1), in backward order. 

Code (Java):

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (n == 0) {
            result.add(0);
            return result;
        }
        
        List<Integer> lastGray = grayCode(n - 1);
        int addOnNum = 1 << (n - 1);
        
        result.addAll(lastGray);
        
        for (int i = lastGray.size() - 1; i >= 0; i--) {
            result.add(lastGray.get(i) + addOnNum);
        }
        
        return result;
    }
}

Update on 8/1/2018:

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        
        if (n <= 0) {
            ans.add(0);
            return ans;
        }
        
        ans.add(0);
        ans.add(1);
        
        for (int i = 2; i <= n; i++) {
            int size = ans.size();
            for (int j = size - 1; j >= 0; j--) {
                ans.add(ans.get(j) + (1 <<(i - 1)));
            }
        }
        
        return ans;
    }
}

Leetcode: Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Understand the problem:
A histogram problem very similar to container with most water and trapping rain water problems. So the first thing is to come out the area of the histograms, which could be calculated as area = (j - i + 1) * min(A[i], A[j]). Thus the most straight-forward way is to try each pair of i and j, and get its area, as well as its largest area. 

A wrong Solution:
As described above, the most straight-forward way is to iterate through all possible i and j, and calculate the area. So the time complexity is O(n^2) for this solution. 

Code (Java):

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height.length; j++) {
                int area = (j - i + 1) * Math.min(height[i], height[j]);
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

The height = [2,1,5,6,2,3], generated the result of 12, instead of 10. The reason is because the area calculation equation was wrong. For a pair of i, j, its area is not determined by the min (A[i], A[j])., but minimum A[k], i <= i <= j.  

The correct Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            int minV = height[i];
            for (int j = i; j < height.length; j++) {
              minV = Math.min(minV, height[j]);  
              int area = (j - i + 1) * minV;
                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        
        return maxArea;
    }
}

A better Solution:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        if (height.length == 1) {
            return height[0];
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int[] copy = new int[height.length + 1];
        copy = Arrays.copyOf(height, height.length + 1);
        
        int maxArea = 0;
        int i = 0;
        
        while (i < copy.length) {
            if (stack.isEmpty() || copy[i] > copy[stack.peek()]) {
                stack.push(i);
                i++;
            } else {
                int index = stack.pop();
                int localArea = copy[index] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, localArea);
            }
        }
        
        return maxArea;
    }
}

Leetcode: Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Understand the problem:
The problem asks for reversing a linked list from position m to n. Note that 1 <= m <= n <= length. The problem also requires for in-place and one-pass traversal of the linked list. 

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        head = dummyNode;
        
        ListNode prev = dummyNode;
        ListNode start = dummyNode.next;
        ListNode end = dummyNode.next;
        
        // move end pointer n - m steps ahead;
        for (int i = 0; i < n - m; i++) {
            end = end.next;
        }
        
        // move all the three pointers to m - 1 steps
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
            start = start.next;
            end = end.next;
        }
        
        ListNode nextNode = end.next;
        end.next = null;
        
        // Reverse linked list from start to end
        ListNode newHead = reverseList(start);
        
        prev.next = newHead;
                
        start.next = nextNode;
        
        return dummyNode.next;
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr= head;
        
        while (curr != null) {
            ListNode nextNode = curr.next;
            
            curr.next = prev;
            prev = curr;
            
            curr = nextNode;
        }
        
        return prev;
    }
}

Update 10/8/14:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next  = head;
        
        int count = 1;
        /// Find the tail node of the first segment
        ListNode firstTail = dummyNode;
        while (count < m) {
            firstTail = firstTail.next;
            count++;
        }
        
        /// reverse the middle segement
        ListNode midTail = firstTail.next;
        ListNode midHead = firstTail.next;
        
        ListNode prev = null;
        int num = n - m + 1;
        int i = 0;
        while (i < num) {
            ListNode next = midHead.next;
            midHead.next = prev;
            prev = midHead;
            midHead = next;
            i++;
        }
        
        /// Link with the third segment
        firstTail.next = prev;
        midTail.next = midHead;
        
        return dummyNode.next;
        
    }
}

Leetcode: Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Understand the problem:
The problem asks for if a Word exists in the board, where the word can be constructed from letters of sequentially adjacent cell. Note that the same letter cell may not be used more than once, which means the solution cannot contain a circle. 

Solution:
The problem could be still categorized as a permutation and combination problem. The only thing to note is each cell can only be visited once, so we need to use an array to mark each visited cell.

Code (Java):

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || word == null) {
            return true;
        }
        
        if (board.length == 0 && word.length() == 0) {
            return true;
        }
        
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (existHelper(board, word, 0, i, j, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean existHelper(char[][] board, String word, int start, int row, int col, boolean[][] visited) {
        if (start == word.length()) {
            return true;
        }
        
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) {
            return false;
        }
        
        if (visited[row][col]) {
            return false;
        }
        
        if (board[row][col] != word.charAt(start)) {
            return false;
        }
        
        visited[row][col] = true;
        boolean result = existHelper(board, word, start + 1, row - 1, col, visited) ||
                         existHelper(board, word, start + 1, row + 1, col, visited) ||
                         existHelper(board, word, start + 1, row, col - 1, visited) ||
                         existHelper(board, word, start + 1, row, col + 1, visited);
        visited[row][col] = false;
        
        return result;
    }
}

Leetcode: Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Understand the problem:
The problem asks for finding the minimum window substring. Note that the time complexity should be in O(n) time. 

Naive Approach:
A very straight-forward solution could be save the characters of T into a hashset, then iterate though the string from beginning. When found an existed character at the hashset, we delete that one until the hashset is empty, which means we found the string that contains all the characters in T. Note that the T string could contain duplicated characters, so we must use a hash map to save its number of occurrence. If the number of occurrence equals to 1, we delete that key. 

For this algorithm, it will take O(n^2) time because we found all substrings that fulfill the requirements, of each times O(n) time.  

Code (Java):

public class Solution {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return "";
        }
        
        HashMap<Character, Integer> hashMap = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++) {
            if (hashMap.containsKey(T.charAt(i))) {
                int freq= hashMap.get(T.charAt(i)) + 1;
                hashMap.put(T.charAt(i), freq);
            } else {
                hashMap.put(T.charAt(i), 1);
            }
        }
        
        int start = 0;
        int min = Integer.MAX_VALUE;
        String result = "";
        while (start < S.length()) {
            HashMap<Character, Integer> currMap = new HashMap<Character, Integer>(hashMap);
            int end = start; 
            
            while (end < S.length() && !currMap.isEmpty()) {
                if (currMap.containsKey(S.charAt(end))) {
                    if (currMap.get(S.charAt(end)) == 1) {
                        currMap.remove(S.charAt(end));
                    } else {
                        int freq = currMap.get(S.charAt(end));
                        currMap.put(S.charAt(end), freq - 1);
                    }
                }
                end++;
            }
            
            if (currMap.isEmpty() && (end - start < min)) {
                min = end - start;
                result = S.substring(start, end);
            }
            
            start++;
        }
        
        return result;
    }
}

Not surprisingly, it got the TLE error. So we need to find out a linear time solution.

A better Solution:
The idea of the linear solution is first to find out a substring window that contains all characters of the T string. Then we shrink the window by moving forward of the start pointer. The rule is we can move on the start point if the character at start is not in the hash map, or the hash map still contains a full set of target characters even after we remove it. 

Code (Java):

public class Solution {
    public String minWindow(String S, String T) {
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return "";
        }
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
        
        for (int i = 0; i < T.length(); i++) {
            map.put(T.charAt(i), 0);
            
            if (dict.containsKey(T.charAt(i))) {
                dict.put(T.charAt(i), dict.get(T.charAt(i)) + 1);
            } else {
                dict.put(T.charAt(i), 1);
            }
        }
        
        int start = 0;
        int count = 0;
        int minLen = S.length() + 1;
        String result = "";
        
        for (int end = 0; end < S.length(); end++) {
            if (map.containsKey(S.charAt(end))) {
                map.put(S.charAt(end), map.get(S.charAt(end)) + 1);
                
                if (map.get(S.charAt(end)) <= dict.get(S.charAt(end))) {
                    count++;
                }
            }
            
            if (count == T.length()) {
                while (!dict.containsKey(S.charAt(start)) || 
                  map.get(S.charAt(start)) > dict.get(S.charAt(start))) {
                    if (map.containsKey(S.charAt(start))) {
                        map.put(S.charAt(start), map.get(S.charAt(start)) -1);
                    }
                    start++;
                } 
            
                if (end - start + 1 < minLen) {
                    minLen = end - start + 1;
                    result = S.substring(start, end + 1);
                }
            }
        }
        
        return result;
    }
}

Discussion:
Note that we used two hash map because there might be duplicated characters in the T string. So the initial number of occurrence for each character may not be 1. Therefore when we determine the count, which is to decide if the current window contains all characters in the T, we cannot simply check each character occurred more than once.   
Summary:
This is another dictionary related question. For this kind of question, it is naturally to use hash Map. 

Leetcode: Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Understand the problem:
The problem is an extension to the I. Since duplicates exist in the array, cutting the array into two halves will not work. Consider [1,3,1,1,1], target is 3, it will not find the targeted number. 

Solution:

public class Solution {
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (A[mid] == target) {
                return true;
            }
            
            if (A[lo] < A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else if (A[lo] > A[mid]) {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            } else {
                lo++;
            }
        }
        
        return false;
    }
}

Update on 9/29/14:
If we directly use the original code from problem I, we will get errors. For example, for the input array [1, 3, 1, 1, 1], and target = 3. Now the situation is A[lo] = A[mid] = A[hi], so we are unable to say the first half is in ascending order. 

Code (Java):

public class Solution {
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (A[mid] == target) {
                return true;
            }
            
            if (A[lo] < A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else if (A[lo] > A[mid]) {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            } else {
                lo++;
            }
        }
        
        if (A[lo] == target || A[hi] == target) {
            return true;
        }
        
        return false;
    }
}

The take-away message for this problem:
1. Figure out why the solution of problem 1 won't work. Take out an opposite example. 
A = [3, 1, 2, 3, 3, 3, 3], where A[lo] == A[mid] == A[hi]
2. Analyze the time complexity in worst case, why it is O(n). Take an example. 
A = [1, 1, 1, 1, 1, 1], where target = 2, then you need to iterate all elements of the array
A = [1, 1, 1, 1, 1, 0], where the target = 0, then you need to iterate all elements as well.

Updates on 11/20/14:

public class Solution {
    public boolean search(int[] A, int target) {
  if (A == null || A.length == 0) {
   return false;
        }

        int lo = 0;
        int hi = A.length - 1;
        while (lo + 1 < hi) {
         int mid = lo + (hi - lo) / 2;
         if (A[mid] == target) {
             return true;
            }
         
         if (A[lo] < A[mid]) {
          if (target >= A[lo] && target < A[mid]) {
                 hi = mid;
                } else {
                 lo = mid;
                }
                
            } else if (A[mid] < A[hi]) {
             if (target > A[mid] && target <= A[hi]) {
              lo = mid;
                } else {
                 hi = mid;
                }
            } else {
                if (A[lo] == target) {
                    return true;
                }
             lo++;
            }
        }
        if (A[lo] == target || A[hi] == target) {
         return true;
        } else {
         return false;
        }
    }
}

The difference is to check A[mid] < A[hi] meaning right half is sorted. 
The second difference is when we move the left pointer one step ahead, we need to check if it is equal to the target. 

Leetcode: Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Understand the problem:
A classic permutation and combination problem. So using the recursion is a natural way. 

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        ArrayList<Integer> curr = new ArrayList<Integer>();
        combineHelper(num, 0, 0, k, result, curr);
        
        return result;
    }
    
    private void combineHelper(int[] num, int start, int m, int k, 
        ArrayList<ArrayList<Integer>> result, ArrayList<Integer> curr) {

        if (m == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        

        for (int i = start; i < num.length; i++) {
            curr.add(num[i]);
            combineHelper(num, i + 1, m + 1, k, result, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

Update on 9/25/15:

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<>();
        
        combineHelper(1, n, 0, k, curr, result);
        
        return result;
    }
    
    private void combineHelper(int start, int n, int num, int k, 
       List<Integer> curr, List<List<Integer>> result) {
        if (num == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            curr.add(i);
            combineHelper(i + 1, n, num + 1, k, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}

Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

Understand the problem:
The problem reads likes an application problem. However, if you can abstract from it, it actually gives you an arrays of integers, with the number 0, 1, and 2. For example, 1, 1, 2, 0, 1, 0, 1. Then you are asked to sort it out. Note that you are not allowed to use any sorting libraries like quick sort. 

Naive Solution:
Since you know that the array is composed by only 0s, 1s and 2s. You should naturally think about the bucket sort. There are three buckets, of each contains 0s, 1s, and 2s. The most straight-forward solution is first to count the number of 0s, 1s and 2s respectively. Then in the second pass fill the original array with the number of 0, 1, and 2. 

Code (Java):

public class Solution {
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        
        for (int i = 0; i < A.length; i++) {
            switch(A[i]) {
                case 0: ++num0;
                        break;
                case 1: ++num1;
                        break;
                case 2: ++num2;
                        break;
            }
        }
        
        int j = 0;
        for (j = 0; j < num0; j++) {
            A[j] = 0;
        }
        
        for (j = 0; j < num1; j++) {
            A[num0 + j] = 1;
        }
        
        for (j = 0; j < num2; j++) {
            A[num0 + num1 + j] = 2;
        }
    }
}

A better approach:
The question asks for solving the problem using only one pass of the array. Since the array is only composed of 0, 1, and 2, we can naturally think of using two pointers approach. We use two pointers, red and blue, points to the starting and end of the array initially. Then iterate index i from 0 to the end of the array. If A[i] == 0, move it to red pointer. If A[i] == 2, move it to blue pointer. Else move on. 

Code (Java):

public class Solution {
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int red = 0;
        int blue = A.length - 1;
        
        int i = 0;
        while (i <= blue) {
            if (A[i] == 0) {
                swap(A, i, red);
                red++;
                i++;
            } else if (A[i] == 2) {
                swap(A, i, blue);
                blue--;
            } else {
                i++;
            }
        }
    }
    
    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Discussion:
Note that the increase of index i. For A[i] == 0, we must increase the index of i once we swap A[i] and A[red], because i cannot be less than red. For the A[i] == 2, we don't need to increase i, since now A[i] could be possible 0 since it is swapped with 2. We need to check that number.

Summary:
This problem is actually a 3-way partition problem. 

Leetcode: Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Understand the problem:
The problem asks for a minimum edit distance from string 1 to string 2. E.g. 
a => b, the minimum edit distance is 1
ab => bc, the minimum edit distance is 2
abc => acd, the output is 2

Since solving this problem using recursion will take the runtime at exponential order, we should naturally think about the DP solution. The key of the DP solution is to define the dp array as well as the transit equation.

Solution:
We use a 2D DP dp[i][j] denotes the minimum edit distance from substring[0, i] to substring[0, j]. So we wanna check the last element of the DP, which stands for the minimum distance from string 1 to string 2. 

The initial state, dp[0][j] = j, dp[i][0] = i. Means the minimum edit distance from empty string to string j and i is length of j and i, respectively. 

For dp[i][j], if word1.charAt(i) == word2.charAt(j), dp[i][j] = dp[i - 1][j - 1]. 
Else, there are three cases you must consider:

• Replace the word1.charAt(i) to word2.charAt(j), so dp[i][j] = dp[i - 1][j - 1] + 1. E.g. abd, abc, when i points to d and j points to c, its minimum edit distance equals to replacing d with c, which is the minimum edit distance from ab to ab plus 1. 
• Insert at word1.charAt(i) to word2.charAt(j), which equals to delete at word2.charAt(j). So dp[i][j] = dp[i][j - 1] + 1. E.g. ab to abc
• Delete at word1.charAt(i) to word2.charAt(j). So dp[i][j] = dp[i - 1][j]. E.g. abc to ab.
• We choose the minimum number from the above three cases. 

Code (Java):

public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word1.length() == 0) {
            return word2.length();
        }
        
        if (word2 == null || word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // update the first row
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
        
        // update the first column
        for (int j = 1; j <= m; j++) {
            dp[j][0] = j;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int replace = dp[i - 1][j - 1] + 1;
                    int insert = dp[i][j - 1] + 1;
                    int delete = dp[i - 1][j] + 1;
                    
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        
        return dp[m][n];
    }
}

Summary:
The problem is a bit of trickier than other DP problems like unique path, but still could be categorized as one kind of problems. The challenge part of a DP problem is to construct the transit equation. 


Update on 3/25/19: O(n) space solution

public class Solution {
    /**
     * @param word1: A string
     * @param word2: A string
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        
        if (word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[2][n + 1];
        int old = 0;
        int cur = 1;
        
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        
        for (int i = 1; i <= word1.length(); i++) {
            dp[cur][0] = i;
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[cur][j] = dp[old][j - 1];
                } else {
                    dp[cur][j] = Math.min(dp[old][j - 1], Math.min(dp[old][j], dp[cur][j - 1])) + 1;
                }
            }
            
            old = cur;
            cur = 1 - cur;
            
        }
        
        return dp[old][n];
    }
}