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.


Two dimentional dynamic programming
map[i][j] = true if s1[0,i-1] and s2[0,j-1] interleaves into s3[0,i+j-1].

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s3.length() != s1.length() + s2.length())
            return false;
       
        boolean[][] mat = new boolean[s1.length() +1][s2.length()+1];
        for(int i = 0; i < mat.length; i++){
            for(int j = 0; j < mat[i].length; j++)
                mat[i][j] = false;
        }
        mat[0][0] = true;
       
        for(int i = 1; i <= s1.length(); i++){
            if(s1.charAt(i-1) == s3.charAt(i-1)){
                mat[i][0] = true;
            }
            else break;
        }
       
        for(int i = 1; i <= s2.length(); i++){
            if(s2.charAt(i-1) == s3.charAt(i-1)){
                mat[0][i] = true;
            }
            else break;
        }
       
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                char c1 = s1.charAt(i-1);
                char c2 = s2.charAt(j-1);
                char c3 = s3.charAt(i+j-1);
                if(c1 == c3) mat[i][j] |= mat[i-1][j];
                if(c2 == c3) mat[i][j] |= mat[i][j-1];
            }
        }
        return mat[s1.length()][s2.length()];
       
    }
}

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.


using a stack, when the next height is larger, push its position into the stack, otherwise, pop a position and calculate the area of the maximum rectangle that can be formed using the height at the position.

remember: the bar right next to the top position at the stack after pop is always larger or equal to the bar at the poped position.


public class Solution {
    public int largestRectangleArea(int[] height) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(height==null || height.length == 0) return 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
     
        stack.add(0);
        int i = 1;
        int ret = height[0];
        while( i < height.length + 1){
            int nextv = i < height.length? height[i] : 0;
            if(stack.isEmpty() || height[stack.getLast()] <= nextv)
            {
                stack.add(i++);
            }
            else{
                int t = stack.removeLast();
                ret = Math.max(ret, height[t] * (stack.isEmpty() ? i : i-1-stack.getLast()) );
            }
        }
        return ret;
     
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!




public class Solution {
    public int trap(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length==0) return 0;
        int i = 0; int j = A.length-1;
        int lm = A[i]; int rm = A[j];
       
        int sum = 0;
       
        while(i<j){
            if(lm <= rm){
                if(A[++i] < lm) sum += lm - A[i];
                else lm = A[i];
            }
            else{
                if(A[--j] < rm) sum += rm - A[j];
                else rm = A[j];
            }
        }
        return sum;
    }
}

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.


make an inorder traversal, if the value is increasing, it is a BST.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode pre;
    private boolean ret;
    void inorder(TreeNode root){
        if(ret == false) return;
        if(root==null) return;
       
        inorder(root.left);
        if(pre == null){ pre = root;}
        else{
            if(pre.val >= root.val){
                ret = false;
                return;
            }
            pre = root;
        }
        if(ret) inorder(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        pre = null;
        ret = true;
        inorder(root);
        return ret;
    }
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.


firstorder the value will increase, so we can find the first error

backorder the value will decrease, so we can find the second error.

change it 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode first;
    TreeNode second;
    private TreeNode pre;
    void inorder(TreeNode root){
        if(first != null) return;
        if(root == null) return;
        inorder(root.left);
        if(pre == null) pre=root;
        else{
            if(pre.val > root.val) {
                first = pre; return;
            }
            pre = root;
        }
        if(first == null)
            inorder(root.right);
    }
    void backorder(TreeNode root){
        if(second != null) return;
        if(root == null) return;
        backorder(root.right);
        if(pre == null) pre = root;
        else{
            if(pre.val < root.val) {
                second = pre;
                return;
            }
            pre = root;
        }
        if(second == null)
            backorder(root.left);
    }
   
    public void recoverTree(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        first = null;
        second = null;
       
        pre = null;
        inorder(root);
       
        pre = null;
        backorder(root);
       
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.


Find the root, using recursive.

Note:
You may assume that duplicates do not exist in the tree.
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode buildTree(int[] a, int a1, int a2, int[] b, int b1, int b2){
        if(a1 > a2 || b1 > b2) return null;
        int rootval = b[b2];
        int posA = a1;
        while(posA <= a2){
            if(a[posA] == rootval) break;
            posA++;
        }
       
        TreeNode root = new TreeNode(rootval);
        int posB = b1 + posA - 1 - a1;
        TreeNode.left = buildTree(a,a1,posA-1,b, b1, posB);
        TreeNode.right = buildTree(a,posA+1,a2,b, posB+1,b2-1);
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(inorder.length == 0) return null;
        //return null;
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
       
    }
}

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


Recursively build the tree.

public class Solution {
   
    TreeNode sortToBST(ListNode[] list, int start, int end){
        if(start > end) return null;
       
        int mid = (start + end) / 2;
        TreeNode leftchild = sortToBST(list, start, mid-1);
        TreeNode parent = new TreeNode(list[0].val);
        parent.left = leftchild;
        list[0] = list[0].next;
        parent.right = sortToBST(list,mid+1, end);
        return parent;
    }
   
    public TreeNode sortedListToBST(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode[] l = new ListNode[1];
        l[0] = head;
        int len = 0;
        while(head!=null){
            len ++; head = head.next;
        }
        return sortToBST(l,0,len-1);
    }
}

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each paths sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

traverse the whole tree, then we get the answer.

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> ret;
    ArrayList<Integer> tran;
    void buildPath(TreeNode root, int sum){
        if(root.left == null && root.right == null){
            if(sum == root.val){
                ArrayList<Integer> n = new ArrayList<Integer>(tran);
                n.add(root.val);
                ret.add(n);
            }
            return;
        }
        tran.add(root.val);
        if(root.left != null) buildPath(root.left,sum - root.val);
        if(root.right != null) buildPath(root.right, sum - root.val);
        tran.remove(tran.size()-1);
    }
   
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ret = new ArrayList<ArrayList<Integer>>();
        tran = new ArrayList<Integer>();
        if(root == null) return ret;
        buildPath(root, sum);
        return ret;
    }
}

Flatten Binary Tree to Linked List

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

recursive

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null) return;
        flatten(root.left);
        flatten(root.right);
       
        TreeNode p = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode q = root;
        while(q.right != null) q = q.right;
        q.right = p;
    }
}

Distinct Subsequences

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.


let f_ij be the number of distinct subsequences of T[0,j] in S[0,i], then
f_i+1,j = S[i+1] == T[j] ? f_{i,j-1} + f_{i,j} : f_{i,j}


public class Solution {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(S.length() ==0 ) return 0;
        assert T.length() >0;
       
        int[] dp = new int[T.length()];
        for(int i = 0; i < dp.length; i++) dp[i] = 0;
       
        for(int i =0 ; i < S.length() ; i++){
            for(int j = T.length()-1; j>=0; j--){
                if(T.charAt(j) == S.charAt(i)){
                    dp[j] += j>0 ? dp[j-1] : 1;
                }
            }
        }
        return dp[T.length()-1];
    }
}

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

For any value in loc i in array A, it takes only O(1) time to determine whether it is the median: only need to check whether there are exact amount of numbers in array B that are less than the value.

class Solution {
    int[] A;
    int[] B;
   
    double median(int A[]){
        if(A.length % 2 == 0)
            return 0.5 * (A[A.length/2 -1] + A[A.length/2]);
        else
            return A[A.length/2];
    }
   
    double med(int small, int large){
        if((A.length + B.length) % 2 == 0)
            return 0.5*(double)(small + large);
        else return Math.max(small,large);
    }
   
    double find(int A[], int B[], int left,int right){
       
        if(left > right) return find(B,A,0,B.length-1);
        int mid = left + (right-left+1)/2;
        int r1 = mid + 1;
        int r2 = (A.length + B.length)/2 - r1;
       
        if(r2 > B.length) return find(A,B,mid+1,right);
        else if (r2 < 0) return find(A,B,left,mid-1);
        else if (r2 == 0){
            if(A[mid] <= B[0]) {
                int min = B[0];
                if(mid+1<A.length) if(min > A[mid+1]) min = A[mid+1];
                return med(A[mid],min);
            }
            else return find(A,B,left,mid-1);
        }
       
        if(B[r2-1] <= A[mid]){
            if(r2 > B.length-1){
                return med(A[mid],A[mid+1]);
            }
            else if(B[r2] >= A[mid]){
                int min = 0;
                if(mid+1>A.length-1){
                    min = B[r2];
                }
                else{
                    min = Math.min(A[mid+1],B[r2]);
                }
                return med(A[mid],min);
               
            }
            else {
                return find(A,B,left,mid-1);
            }
        }
        else{
            return find(A,B,mid+1,right);
        }
       
    }
   
    public double findMedianSortedArrays(int A[], int B[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        this.A = A; this.B=B;
        if(B.length == 0){
           return median(A);
        }
        else if(A.length == 0) return median(B);
       
        return find(A,B,0,A.length-1);
    }
}

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.

From top to down, build link to each level
remember: you have build right pointer of the previous level, so you can access all nodes in the previous level


/**
 * 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) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null) return;
        TreeLinkNode l = null;
        TreeLinkNode p = null;
        TreeLinkNode head = new TreeLinkNode(0);
       
        while(root != null){
            l = root;
            head.next = null;
            p = head;
            while(l!=null){
                if(l.left!=null) {
                    p.next = l.left; p = p.next;
                }
                if(l.right!=null){
                    p.next = l.right; p = p.next;
                }
                l = l.next;
            }
            root = head.next;
        }
       
    }
}

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Using DP, calculate the minimal path sum from bottom to top.
Using an array to restore the partial result.

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int height = triangle.size()-1;
        int[] ret = new int[height + 1];
        for(int i = 0; i<triangle.get(height).size(); i++){
            ret[i] = triangle.get(height).get(i);
        }
        while(--height >=0){
            for(int i = 0; i<triangle.get(height).size();i++){
                int val = triangle.get(height).get(i);
                val += Math.min(ret[i],ret[i+1]);
                ret[i] = val;
            }
        }
        return ret[0];
    }
}