75. Search for a Range

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] res = new int[2];
        res[0] = Integer.MAX_VALUE;
        res[1] = Integer.MIN_VALUE;
       
        range(A, target, 0, A.length-1, res);
       
        if (res[0]==Integer.MAX_VALUE||res[1]==Integer.MIN_VALUE) {
            res[0] = -1;
            res[1] = -1;
        }
       
        return res;
    }
   
    public void range(int[] A, int target, int low, int high, int[] res) {
        if (low>high) return;
       
        int mid = (low+high)/2;
       
        if (A[mid]==target) {
            res[0] = Math.min(res[0], mid);
            res[1] = Math.max(res[1], mid);
            range(A, target, low, mid-1, res);
            range(A, target, mid+1, high, res);
        } else if (A[mid]<target) range(A, target, mid+1, high, res);
        else range(A, target, low, mid-1, res);
    }
}

74. 4Sum

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        Set<ArrayList<Integer>> res = new HashSet<ArrayList<Integer>> ();
       
        Arrays.sort(num);
       
        for (int i=0; i<num.length-3; i++) {
            for (int j=i+1; j<num.length-2; j++) {
                int m = j+1;
                int n = num.length-1;
               
                while (m<n) {
                    if (num[i]+num[j]+num[m]+num[n]==target) {
                        ArrayList<Integer> temp = new ArrayList<Integer> ();
                        temp.add(num[i]);
                        temp.add(num[j]);
                        temp.add(num[m]);
                        temp.add(num[n]);
                        res.add(temp);
                        m++;
                        n--;
                    } else if (num[i]+num[j]+num[m]+num[n]<target) m++;
                    else n--;
                }
            }
        }
       
        return new ArrayList<ArrayList<Integer>> (res);
    }
}

73. 3Sum Closest

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if (num.length==3) return num[0]+num[1]+num[2];
       
        int res = num[0]+num[1]+num[2];
        int min = Integer.MAX_VALUE;
        int i, j, p;
       
        Arrays.sort(num);
     
        for (i=0; i<num.length-2; i++) {
            j = i+1;
            p = num.length-1;
         
            while (j<p) {
                int temp = num[i]+num[j]+num[p];
             
                if (temp==target) return target;
                else if (Math.abs(temp-target)<min) {
                    min = Math.abs(temp-target);
                    res = temp;
                }
               
                if (temp<target) j++;
                else p--;
            }
        }
     
        return res;
    }
}

72. 3Sum

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> temp = new ArrayList<Integer> ();
       
        if (num==null) return null;
       
        int i, j, p, i_val=Integer.MAX_VALUE, j_val, p_val, sum;
        Arrays.sort(num);
       
        for (i=0; i<num.length-2; i++) {
            if (num[i]==i_val) continue;
            i_val = num[i];
            j = i+1;
            p = num.length-1;
           
            while (j<p) {
                sum = num[i]+num[j]+num[p];
                j_val = num[j];
                p_val = num[p];
               
                if (sum==0) {
                    temp.clear();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[p]);
                    res.add((ArrayList<Integer>) temp.clone());
                    while (++j<p && num[j]==j_val);
                } else if (sum>0) {
                    while (j<--p && num[p]==p_val);
                } else {
                    while (++j<p && num[j]==j_val);
                }
            }
        }
       
        return res;
    }
}

71. Longest Common Prefix

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length==0) return "";
       
        int minLen = strs[0].length();
        int minIndex = 0;
       
        for (int i=1; i<strs.length; i++) {
            if (strs[i].length()<minLen) {
                minLen = strs[i].length();
                minIndex = i;
            }
        }
       
        String s = strs[minIndex];
        int i;
       
        for (i=0; i<s.length(); i++) {
            boolean mark = true;
            for (int j=0; j<strs.length; j++) {
                if (!strs[j].substring(0, i+1).equals(s.substring(0, i+1))) {
                    mark = false;
                    break;
                }
            }
            if (mark==false) return s.substring(0,i);
        }
       
        return s.substring(0,i);
    }
}

70. Jump Game II

public class Solution {
    public int jump(int[] A) {
        int count = 0;
        int dest = A.length-1;
       
        while (dest!=0) {
            for (int i=0; i<A.length; i++) {
                if (A[i]+i>=dest) {
                    dest = i;
                    count++;
                    break;
                }
            }
        }
       
        return count;
    }
 }

69. Jump Game

public class Solution {
    public boolean canJump(int[] A) {
        int [] state = new int[A.length];
     
        state[0] = A[0];
        if (state[0]==0 && A.length>1) return false;
     
        for (int i=1; i<A.length; i++) {
            state[i] = Math.max(state[i-1], A[i]+i);
            if (state[i]==i && i!=A.length-1) return false;
        }
     
        return true;
    }
}

68. Flatten Binary Tree to Linked List

 /**
 * 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) {
        rec(root);
    }
   
    public TreeNode rec(TreeNode root) {
        if (root==null) return root;
       
        TreeNode leftsub = rec(root.left);
        TreeNode rightsub = rec(root.right);
       
        root.left = null;
        root.right = leftsub;
       
        TreeNode rightmost = leftsub;
       
        if(rightmost!=null) {
            while (rightmost.right!=null) {
                rightmost = rightmost.right;
            }
        }
       
        if (rightmost!=null) rightmost.right = rightsub;
        else root.right = rightsub;
       
        return root;
    }
}

67. Longest Consecutive Sequence

public class Solution {
    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer> ();
       
        for (int i:num) set.add(i);
       
        int max = 0;
       
        for (int i=0; i<num.length; i++) {
            if (set.contains(num[i])) {
                int next = num[i]-1;
                int count = 1;
                set.remove(num[i]);
                while (set.contains(next)) {
                    set.remove(next);
                    next--;
                    count++;
                }
                next = num[i]+1;
                while (set.contains(next)) {
                    set.remove(next);
                    next++;
                    count++;
                }
                max = Math.max(max, count);
            }
        }
       
        return max;
    }
}

66. Subsets II

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>> ();
        Arrays.sort(num);
        int length = num.length;
       
        for (int i=0; i<Math.pow(2, length); i++) {
            ArrayList<Integer> temp = new ArrayList<Integer> ();
            int t = i;
           
            for (int j=0; j<length; j++) {
                int bit = t&1;
                if (bit==1) temp.add(num[j]);
                t = t>>1;
            }
            set.add(temp);
        }
       
        return new ArrayList<ArrayList<Integer>> (set);
    }
}

65. Subsets

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        Arrays.sort(S);
        int length = S.length;
       
        for (int i=0; i<Math.pow(2, length); i++) {
            ArrayList<Integer> temp = new ArrayList<Integer> ();
            int t = i;
           
            for (int j=0; j<length; j++) {
                int bit = t&1;
                if (bit==1) temp.add(S[j]);
                t = t>>1;
            }
            res.add(temp);
        }
       
        return res;
    }
}

64. Valid Sudoku

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        return row(board) && col(board) && box(board);
    }
   
    public boolean row(char[][] board) {
        for (int i=0; i<9; i++) {
            boolean[] flag = new boolean[10];
            for (int j=0; j<9; j++) {
                if (markflag(flag, board[i][j])) return false;
            }
        }
        return true;
    }
   
    public boolean col(char[][] board) {
        for (int i=0; i<9; i++) {
            boolean[] flag = new boolean[10];
            for (int j=0; j<9; j++) {
                if (markflag(flag, board[j][i])) return false;
            }
        }
        return true;
    }
   
    public boolean box(char[][] board) {
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                boolean[] flag = new boolean[10];
                for (int m=0; m<3; m++) {
                    for (int n=0; n<3; n++) {
                        if (markflag(flag, board[i*3+m][j*3+n])) return false;
                    }
                }
            }
        }
        return true;
    }
   
    public boolean markflag(boolean[] flag, char c) {
        if (c=='.') return false;
        int index = c-'0';//convert char to int
        if (flag[index]) return true;
        else {
            flag[index]=true;
            return false;
        }
    }
}

63. Valid Parentheses

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character> ();
       
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{') stack.push(s.charAt(i));
            else {
                if (stack.empty()) return false;
                Character temp = stack.peek();
                if (s.charAt(i)==')' && temp!='(') return false;
                if (s.charAt(i)==']' && temp!='[') return false;
                if (s.charAt(i)=='}' && temp!='{') return false;
                stack.pop();
            }
        }
       
        return stack.empty();
    }
}

62. Trapping Rain Water

public class Solution {
    public int trap(int[] A) {
        if (A.length==0) return 0;
       
        int[] left = new int[A.length];
        int[] right = new int[A.length];
        int res = 0;
       
        left[0] = A[0];
        for (int i=1; i<A.length; i++) {
            left[i] = A[i]>left[i-1]?A[i]:left[i-1];
        }
       
        right[A.length-1] = A[A.length-1];
        for (int i=A.length-2; i>=0; i--) {
            right[i] = A[i]>right[i+1]?A[i]:right[i+1];
        }
       
        for (int i=1; i<A.length-1; i++) {
            res+=Math.min(left[i], right[i])-A[i];
        }
       
        return res;
    }
}

61. Length of Last Word

public class Solution {
    public int lengthOfLastWord(String s) {
        if (s.length()==0) return 0;
       
        int length = 0;
        int i = s.length()-1;
       
        while (i>=0 && s.charAt(i)==' ') i--;
        while (i>=0 && s.charAt(i)!=' ') {
            length++;
            i--;
        }
       
        return length;
    }
}

60. Minimum Depth of Binary Tree

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root==null) return 0;
       
        if (root.left!=null && root.right!=null) return 1+Math.min(minDepth(root.left), minDepth(root.right));
        else if (root.left!=null) return 1+minDepth(root.left);
        else if (root.right!=null) return 1+minDepth(root.right);
        else return 1;
    }
}

59. Palindrome Number

public class Solution {
    public boolean isPalindrome(int x) {
if (x < 0) return false;

// initialize how many zeros
int div = 1;
while (x / div >= 10) {
div *= 10;
}

while (x != 0) {
int left = x / div;
int right = x % 10;

if (left != right)
return false;

x = (x % div) / 10;
div /= 100;
}

return true;
    }
}

58. Sum Root to Leaf Numbers

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        return sum(root, 0);
    }
   
    public int sum(TreeNode root, int temp) {
        if (root==null) return 0;
        temp = 10*temp + root.val;
        if (root.left==null && root.right==null) return temp;
        return (sum(root.left, temp) + sum(root.right, temp));
    }
}

57. Populating Next Right Pointers in Each Node II

/**
 * 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;
         dfs(root);
     }
   
     private void dfs(TreeLinkNode root){
         if(root==null) return;
         if(root.next==null){
             if(root.right!=null) root.right.next=null;
             if(root.left!=null) root.left.next=root.right;
         }else{
             TreeLinkNode p = root.next;
             TreeLinkNode q = null;
             while(p!=null){
                 if(p.left!=null) {q=p.left; break;}
                 if(p.right!=null) {q=p.right; break;}
                 p=p.next;
             }
             if(root.right!=null) root.right.next=q;
             if(root.left!=null&&root.right!=null) root.left.next=root.right;
             if(root.left!=null&&root.right==null) root.left.next=q;
         }
       
         dfs(root.right);
         dfs(root.left);
     }
}

56. Remove Nth Node From End of List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head==null || n==0) return null;
        if (head.next==null && n==1) return null;
       
        ListNode p = head;
        ListNode q = head;
       
        for (int i=0; i<n; i++) {
            if (q!=null) q = q.next;
            else return head;
        }
       
        if (q==null) return head.next;
       
        while (q.next!=null) {
            p=p.next;
            q=q.next;
        }
       
        p.next = p.next.next;
       
        return head;
    }
}

55. Pascal's Triangle II

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

54. Path Sum II

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
       
        if (root==null) return res;
       
        ArrayList<Integer> temp = new ArrayList<Integer> ();
       
        getlist(root, sum, res, temp);
        return res;
    }
   
    public void getlist(TreeNode root, int sum, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp) {
        if (root==null) return;
       
        if (root.left==null && root.right==null && sum-root.val==0) {
            temp.add(root.val);
            res.add((ArrayList<Integer>) temp.clone());
            temp.remove(temp.size()-1);
            return;
        }
       
        temp.add(root.val);
        getlist(root.left, sum-root.val, res, temp);
        getlist(root.right, sum-root.val, res, temp);
        temp.remove(temp.size()-1);
    }
}

53. Path Sum

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root==null) return false;
        if (root.left==null && root.right==null && sum-root.val==0) return true;
        else return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}

52. Combinations

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> temp = new ArrayList<Integer> ();
        getlist(n, k, res, temp, 0);
        return res;
    }
   
    public void getlist(int n, int k, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp, int start) {
        if (temp.size()==k) {
            res.add((ArrayList<Integer>) temp.clone());
            return;
        }
       
        for (int i=start; i<n; i++) {
            temp.add(i+1);
            getlist(n, k, res, temp, i+1);
            temp.remove(temp.size()-1);
        }
    }
}

51. Search in Rotated Sorted Array II

public class Solution {
    public boolean search(int[] A, int target) {
        if (A.length<=0) return false;
        return mySearch(A, 0, A.length-1, target)!=-1;
    }
   
    public int mySearch(int[] A, int head, int back, int target) {
        if (head>back) return -1;
        else {
            int mid=(head+back)/2;
       
            if (target==A[mid]) return mid;
       
            if (A[mid]>A[head]) {
                if (target<=A[mid] && target>=A[head]) return mySearch(A, head, mid-1, target);
                else return mySearch(A, mid+1, back, target);
            }
       
            if (A[mid]<A[head]) {
                if (target<=A[mid] || target>=A[head]) return mySearch(A, head, mid-1, target);
                else return mySearch(A, mid+1, back, target);
            }
           
            if (A[mid]==A[head]) return mySearch(A, head+1, back, target);
       
            return -1;
        }
    }
}

50. Search in Rotated Sorted Array

public class Solution {
    public int search(int[] A, int target) {
        if (A.length<=0) return -1;
        return mySearch(A, 0, A.length-1, target);
    }
   
    public int mySearch(int[] A, int head, int back, int target) {
        if (head>back) return -1;
        else {
            int mid=(head+back)/2;
       
            if (target==A[mid]) return mid;
       
            if (A[mid]>=A[head]) {
                if (target<=A[mid] && target>=A[head]) return mySearch(A, head, mid-1, target);
                else return mySearch(A, mid+1, back, target);
            }
       
            if (A[mid]<A[head]) {
                if (target<=A[mid] || target>=A[head]) return mySearch(A, head, mid-1, target);
                else return mySearch(A, mid+1, back, target);
            }
       
            return -1;
        }
    }
}

49. Remove Duplicates from Sorted Array II

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length<=1) return A.length;
       
        int p=0;
        int q=1;
        int flag=1;
       
        while (q<A.length) {
            if (A[q]==A[p]) {
                flag++;
                if (flag<=2) {
                    p++;
                    A[p] = A[q];
                }
            } else {
                flag=1;
                p++;
                A[p]=A[q];
            }
            q++;
        }
       
        return p+1;
    }
}

48. Set Matrix Zeroes

public class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] m = new boolean[matrix.length];
        boolean[] n = new boolean[matrix[0].length];
       
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (matrix[i][j]==0) {
                    m[i] = true;
                    n[j] = true;
                }
            }
        }
       
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (m[i]==true || n[j]==true) matrix[i][j] = 0;
            }
        }
    }
}

47. Spiral Matrix II

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int level = 0;
        int num = 1;
       
        while(num<n*n) {
            for (int j=level; j<n-1-level; j++) {
                res[level][j] = num;
                num++;
            }
           
            for (int i=level; i<n-1-level; i++) {
                res[i][n-1-level] = num;
                num++;
            }
           
            for (int j=n-1-level; j>level; j--) {
                res[n-1-level][j] = num;
                num++;
            }
           
            for (int i=n-1-level; i>level; i--) {
                res[i][level] = num;
                num++;
            }
           
            level++;
        }
       
        if ((n%2)==1) res[n/2][n/2]=num;
       
        return res;
    }
}

46. Spiral Matrix

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
       
        if (matrix.length==0) return res;
       
        int m = matrix.length;
        int n = matrix[0].length;
       
        order(matrix, m, n, 0, res);
        return res;
    }
   
    public void order(int[][] matrix, int m, int n, int k, ArrayList<Integer> res) {
        if (m<=0 || n<=0) return;
       
        if (m==1) {
            for (int j=0; j<n; j++) {
                res.add(matrix[k][k+j]);
            }
            return;
        }
       
        if (n==1) {
            for (int i=0; i<m; i++) {
                res.add(matrix[k+i][k]);
            }
            return;
        }
       
        //to right
        for (int j=0; j<n-1; j++) {
            res.add(matrix[k][k+j]);
        }
       
        //to down
        for (int i=0; i<m-1; i++) {
            res.add(matrix[k+i][n-1+k]);
        }
       
        //to left
        for (int j=0; j<n-1; j++) {
            res.add(matrix[m-1+k][n-1+k-j]);
        }
       
        //to up
        for (int i=0; i<m-1; i++) {
            res.add(matrix[m-1+k-i][k]);
        }
       
        order(matrix, m-2, n-2, k+1, res);
    }
}

45. Container with most water

public class Solution {
    public int maxArea(int[] height) {
        if (height.length<2) return 0;
       
        int res = 0;
        int i = 0;
        int j = height.length-1;
        int lasti = 0;
        int lastj = 0;
        int localmax = 0;
       
        while (i<j) {
            if (height[i]<height[j]) {
                localmax = (j-i)*height[i];
                if (res<localmax) res = localmax;
                lasti = height[i];
                while (i<j && lasti>=height[i]) {
                    i++;
                }
            } else {
                localmax = (j-i)*height[j];
                if (res<localmax) res = localmax;
                lastj = height[j];
                while (i<j && lastj>=height[j]) {
                    j--;
                }
            }
        }
       
        return res;
    }
}

44. Search a 2D Matrix

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int low = 0;
        int high = matrix.length * matrix[0].length - 1;
       
        while (low <= high) {
            int mid = (low+high)/2;
            int row = mid/matrix[0].length;
            int col = mid%matrix[0].length;
           
            if (target==matrix[row][col]) return true;
            else if (target<matrix[row][col]) high = mid-1;
            else low = mid+1;
        }
       
        return false;
    }
}

43. Minimum Path Sum

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int [][] min = new int[m][n];
       
        min[0][0] = grid[0][0];
       
        for (int i=1; i<m; i++) {
            min[i][0] = min[i-1][0]+grid[i][0];
        }
       
        for (int j=1; j<n; j++) {
            min[0][j] = min[0][j-1]+grid[0][j];
        }
       
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                min[i][j] = Math.min(min[i-1][j], min[i][j-1]) + grid[i][j];
            }
        }
       
        return min[m-1][n-1];
    }
}

42. Linked List Cycle II

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
       
        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
           
            if (fast==slow) {
                slow = head;
               
                while (fast!=slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
               
                return slow;
            }
        }
       
        return null;
    }
}

41. Unique Paths II

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
       
        if (obstacleGrid[m-1][n-1]==1) return 0;
       
        int[][] res = new int[m][n];
        if (obstacleGrid[0][0]==1) return 0;
        res[0][0] = 1;
       
        for (int i=1; i<m; i++) {
            if (res[i-1][0]!=0 && obstacleGrid[i][0]!=1) res[i][0] = 1;
        }
       
        for (int j=1; j<n; j++) {
            if (res[0][j-1]!=0 && obstacleGrid[0][j]!=1) res[0][j] = 1;
        }
       
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                if (obstacleGrid[i][j]!=1) res[i][j] = res[i-1][j] + res[i][j-1];
            }
        }
       
        return res[m-1][n-1];
    }
}

40. Unique Paths

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] res = new int[m][n];
       
        for (int i=0; i<m; i++) {
            res[i][0] = 1;
        }
       
        for (int j=0; j<n; j++) {
            res[0][j] = 1;
        }
       
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                res[i][j] = res[i][j-1] + res[i-1][j];
            }
        }
       
        return res[m-1][n-1];
    }
}

39. Plus One

public class Solution {
    public int[] plusOne(int[] digits) {
        for (int i=digits.length-1; i>=0; i--) {
            if (digits[i]!=9) {
                digits[i]++;
                return digits;
            } else digits[i] = 0;
        }
       
        int[] res = new int[digits.length+1];
        res[0] = 1;
        return res;
    }
}

38. Binary Tree Postorder Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        Stack<TreeNode> stack = new Stack();
     
        if (root==null) return res;
        stack.add(root);
        TreeNode previous = root;
     
        while(!stack.isEmpty()) {
            TreeNode current = stack.peek();
            if ((current.right==null && current.left==null) || current.left==previous || current.right==previous) {
                res.add(current.val);
                stack.pop();
                previous = current;
            } else {
                if (current.right!=null) stack.add(current.right);
                if (current.left!=null) stack.add(current.left);
            }
        }
     
        return res;
    }
}


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        postorder(root, res);
        return res;
    }
   
    public void postorder(TreeNode root, ArrayList<Integer> res) {
        if (root==null) return;
       
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

37. Rotate Image

public class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
       
        for (int i=0; i<len/2; i++) {
            for (int j=0; j<len; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len-1-i][j];
                matrix[len-1-i][j] = temp;
            }
        }
       
        for (int i=0; i<len; i++) {
            for (int j=i+1; j<len; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

36. Permutations II

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> temp = new ArrayList<Integer> ();
       
        Arrays.sort(num);
       
        int len = num.length;
        int[] used = new int[len];
       
        getpermute(num, temp, len, used, res);
        return res;
    }
   
    public void getpermute(int[] num, ArrayList<Integer> temp, int len, int[] used, ArrayList<ArrayList<Integer>> res) {
        if (temp.size()==len) {
            res.add((ArrayList<Integer>) temp.clone());
            return;
        }
       
        for (int i=0; i<len; i++) {
            if (used[i]==0) {
                temp.add(num[i]);
                used[i] = 1;
                getpermute(num, temp, len, used, res);
                used[i] = 0;
                temp.remove(temp.size()-1);
               
                while(i<len-1 && num[i]==num[i+1]) {
                    i++;
                }
            }
        }
    }
}

35. Permutations

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        ArrayList<Integer> temp = new ArrayList<Integer> ();
       
        int len = num.length;
        int[] used = new int[len];
       
        getpermute(num, len, used, temp, res);
        return res;
    }
   
    public void getpermute(int[] num, int len, int[] used, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> res) {
        if (temp.size()==len) {
            res.add((ArrayList<Integer>) temp.clone());
            return;
        }
       
        for (int i=0; i<len; i++) {
            if (used[i]==0) {
                temp.add(num[i]);
                used[i] = 1;
                getpermute(num, len, used, temp, res);
                used[i] = 0;
                temp.remove(temp.size()-1);
            }
        }
    }
}

34. Best Time to Buy and Sell Stock

public class Solution {
    public int maxProfit(int[] prices) {
       
        if (prices.length<2) return 0;
       
        int[] min = new int[prices.length];
        min[0] = prices[0];
        int max = 0;
       
        for (int i=1; i<prices.length; i++) {
            if (prices[i]<min[i-1]) min[i] = prices[i];
            else min[i] = min[i-1];
        }
       
        for (int i=1; i<prices.length; i++) {
            if (max<prices[i]-min[i-1]) max = prices[i] - min[i-1];
        }
       
        return max;
    }
}

33. Generate Parentheses

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
       
        ArrayList<String> res = new ArrayList<String> ();
       
        if (n==0) return res;
       
        gp(n, 0, 0, "", res);
        return res;
    }
   
    public void gp(int n, int left, int right, String temp, ArrayList<String> res) {
       
        if (left<right) return;
       
        if (left==n && right==n) {
            res.add(temp);
            return;
        }
       
        if (left==n) {
            gp(n, left, right+1, temp+")", res);
            return;
        }
       
        gp(n, left+1, right, temp+"(", res);
        gp(n, left, right+1, temp+")", res);
    }
}

32. Binary Tree Level Order Traversal II

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
       
        LinkedList<ArrayList<Integer>> res = new LinkedList<ArrayList<Integer>> ();
        ArrayList<ArrayList<Integer>> res2 = new ArrayList<ArrayList<Integer>> ();
       
        if (root==null) return res2;
       
        ArrayList<Integer> level = new ArrayList<Integer> ();
        int oldCnt = 1;
        int newCnt = 1;
       
        LinkedList<TreeNode> queue = new LinkedList<TreeNode> ();
        queue.add(root);
       
        while (!queue.isEmpty()) {
            oldCnt = newCnt;
            newCnt = 0;
           
            for (int i=0; i<oldCnt; i++) {
                TreeNode n = queue.removeFirst();
                if (n.left!=null) {
                    queue.add(n.left);
                    newCnt++;
                }
                if (n.right!=null) {
                    queue.add(n.right);
                    newCnt++;
                }
                level.add(n.val);
            }
           
            res.addFirst((ArrayList<Integer>) level.clone());
            level.clear();
        }
       
        for (ArrayList<Integer> list: res) res2.add(list);
       
        return res2;
    }
}

31. Binary Tree Level Order Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
               
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
        if (root==null) return res;
       
        ArrayList<Integer> level = new ArrayList<Integer> ();
        int oldCnt = 1;
        int newCnt = 1;
       
        LinkedList<TreeNode> queue = new LinkedList<TreeNode> ();
        queue.add(root);
       
        while (!queue.isEmpty()) {
            oldCnt = newCnt;
            newCnt = 0;
           
            for (int i=0; i<oldCnt; i++) {
                TreeNode n = queue.removeFirst();
                if (n.left!=null) {
                    queue.add(n.left);
                    newCnt++;
                }
                if (n.right!=null) {
                    queue.add(n.right);
                    newCnt++;
                }
                level.add(n.val);
            }
           
            res.add((ArrayList<Integer>) level.clone());
            level.clear();
        }
       
        return res;
    }
}

30. Sort Colors

public class Solution {
    public void sortColors(int[] A) {
        int head = 0;
        int back = A.length - 1;
       
        for (int i=0; i<A.length; ) {
            if (i>back || i<head) break;
            switch (A[i]) {
                case 1:
                    i++;
                    break;
                case 0:
                    swap(A, i, head);
                    i++;
                    head++;
                    break;
                case 2:
                    swap(A, i, back);
                    back--;
                    break;
            }
        }
    }
   
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

29. N-Queens II

public class Solution {
    int res=0;
    public int totalNQueens(int n) {
        if (n<=0) return res;
        int[] loc = new int[n];
        dfs(loc, 0, n);
        return res;
    }
   
    public void dfs(int[] loc, int cur, int n) {
        if (cur==n) {
            res++;
            return;
        }
       
        for (int i=0; i<n; i++) {
            loc[cur] = i;
            if (isValid(loc, cur)) dfs(loc, cur+1, n);
        }
    }
   
    public boolean isValid(int[] loc, int cur) {
        for (int i=0; i<cur; i++) {
            if (loc[cur]==loc[i] || Math.abs(loc[cur]-loc[i])==cur-i) return false;
        }
        return true;
    }
}

28. N-Queens

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<String[]> ();
        int[] loc = new int[n];
        dfs(res, loc, 0, n);
        return res;
    }
   
    public void dfs(ArrayList<String[]> res, int[] loc, int cur, int n) {
        if (cur==n) printBoard(res, loc, n);
        else {
            for (int i=0; i<n; i++) {
                loc[cur] = i;
                if (isValid(loc, cur)) dfs(res, loc, cur+1, n);
            }
        }
    }
   
    public Boolean isValid(int[] loc, int cur) {
        for (int i=0; i<cur; i++) {
            if (loc[i]==loc[cur] || Math.abs(loc[i]-loc[cur])==cur-i) return false;
        }
        return true;
    }
   
    public void printBoard(ArrayList<String[]> res, int[] loc, int n) {
        String[] answer = new String[n];
        for (int i=0; i<n; i++) {
            String row = new String();
            for (int j=0; j<n; j++) {
                if (loc[i]==j) row += "Q";
                else row += ".";
            }
            answer[i] = row;
        }
        res.add(answer);
    }
}

27. Gray Code

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        int size = 1<<n;
        ArrayList<Integer> res = new ArrayList<Integer> ();
       
        for (int i=0; i<size; i++) {
            res.add(i>>1 ^ i);
        }
       
        return res;
    }
}

26. Symmetric Tree

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        return isSymmetric(root.left, root.right);
    }
   
    private boolean isSymmetric(TreeNode tree1, TreeNode tree2) {
        if (tree1==null && tree2==null) return true;
        if ((tree1==null && tree2!=null) || (tree1!=null && tree2==null)) return false;
        if (tree1.val!=tree2.val) return false;
        else return isSymmetric(tree1.left, tree2.right) && isSymmetric(tree1.right, tree2.left);
    }
}

25. Merge Sorted Array

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int count = m+n-1;
        m--;
        n--;
       
        while (m>=0 && n>=0) {
            if (A[m]>B[n]) {
                A[count] = A[m];
                m--;
            } else {
                A[count] = B[n];
                n--;
            }
           
            count--;
        }
       
        while (n>=0) {
            A[count] = B[n];
            n--;
            count--;
        }
    }
}

24. Remove Duplicates from Sorted Array

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length==0) return 0;
        if (A.length==1) return 1;
       
        int p=0;
        int q=1;
       
        while (p<A.length && q<A.length) {
            if (A[q]==A[p]) q++;
            else {
                p++;
                A[p] = A[q];
                q++;
            }
        }
       
        return p+1;
    }
}

23. Convert Sorted Array to Binary Search Tree

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num==null || num.length==0) return null;
        return helper(num, 0, num.length-1);
    }
   
    private TreeNode helper(int[] num, int start, int end) {
        if (start <= end) {
            TreeNode res = new TreeNode(num[(start+end)/2]);
            res.left = helper(num, start, (start+end)/2-1);
            res.right = helper (num, (start+end)/2+1, end);
            return res;
        } else return null;
    }
}

22. Swap Nodes in Pairs

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head==null) return null;
       
        ListNode res = new ListNode(0);
        res.next = head;
        head = res;
       
        while (res.next!=null && res.next.next!=null) {
            ListNode p1 = res.next;
            ListNode p2 = res.next.next;
           
            p1.next = p2.next;
            p2.next = p1;
            res.next = p2;
            res = p1;
        }
       
        return head.next;
    }
}

21. Balanced Binary Tree

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root==null) return true;
        if (Math.abs(maxDepth(root.left)-maxDepth(root.right))>1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
   
    private int maxDepth(TreeNode root) {
        if (root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

20. Pascal's Triangle

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

19. Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null) return l2;
        if (l2==null) return l1;
       
        ListNode p = new ListNode(0);
        p.next = l1;
        l1 = p;
        ListNode q = l2;
       
        while (q!=null) {
            if (p.next!=null) {
                if (q.val<p.next.val) {
                    ListNode temp;
                   
                    temp = p.next;
                    p.next = q;
                    q = q.next;
                    p.next.next = temp;
                } else p = p.next;
            } else {
                p.next = q;
                return l1.next;
            }
        }
       
        return l1.next;
    }
}

18. Remove Element

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A.length==0) return 0;
        if (A.length==1 && A[0]==elem) return 0;
        if (A.length==1 && A[0]!=elem) return 1;
     
        int p = 0;
        int q = A.length - 1;
     
        while (p<q) {
            if (A[p]!=elem) {
                p++;
                continue;
            }
         
            if (A[q]==elem) {
                q--;
                continue;
            }
         
            int temp = A[q];
            A[q] = A[p];
            A[p] = temp;
        }
     
        if (A[p]==elem) return p;
        else return p+1;
    }
}

17. Integer to Roman

public class Solution {
    public String intToRoman(int num) {
        String[] romans = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] nums = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
     
        String res = "";
        int i = 0;
     
        while (num>0) {
            if (num>=nums[i]) {
                num -= nums[i];
                res += romans[i];
            } else i++;
        }
     
        return res;
    }
}

16. Roman to Integer

public class Solution {
    public int romanToInt(String s) {
        if (s==null) return -1;
       
        int res = 0;
       
        for (int i=s.length()-1; i>=0; i--) {
            if (i>0 && transfer(s.charAt(i))>transfer(s.charAt(i-1))) {
                res += transfer(s.charAt(i))-transfer(s.charAt(i-1));
                i--;
            } else res += transfer(s.charAt(i));
        }
       
        return res;
    }
   
    public int transfer(char c) {
        switch(c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
        }
       
        return 0;
    }
}

15. Maximum Subarray

public class Solution {
    public int maxSubArray(int[] A) {
        int max = A[0];
        int[] sum = new int[A.length];
       
        sum[0] = A[0];
       
        for (int i=1; i<A.length; i++) {
            sum[i] = Math.max(sum[i-1]+A[i], A[i]);
            max = Math.max(max, sum[i]);
        }
       
        return max;
    }
}

14. Single Number II

public class Solution {
    public int singleNumber(int[] A) {
        if (A.length<=1) return A[0];
       
        int[] count = new int[32];
        int res = 0;
       
        for (int i=0; i<32; i++) {
            for (int j=0; j<A.length; j++) {
                if (((A[j]>>i)&1)==1) count[i] = (count[i]+1)%3;
            }
            res |= count[i]<<i;
        }
       
        return res;
    }
}

13. Climbing Stairs

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

12. Remove Duplicates From Sorted List

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null || head.next==null) return head;
       
        ListNode dummy = new ListNode(0);
        dummy.next = head;
       
        while (head.next!=null) {
            if (head.val!=head.next.val) head = head.next;
            else head.next = head.next.next;
        }
       
        return dummy.next;
    }
}

11. Search Insert Position

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A.length==0 || A[0]>target) return 0;
       
        int i=0;
        int j=A.length-1;
       
        while(i<j) {
            int mid = (i+j)/2;
            if (A[mid]==target) return mid;
            else if (target<A[mid]) j = mid-1;
            else i = mid+1;
        }
       
        if (target<=A[i]) return i;
        else return i+1;
    }
}

10. Populating Next Right Pointers in Each 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) {
             if(root==null) return;
         root.next=null;
         dfs(root);
     }
   
     private void dfs(TreeLinkNode root){
         if(root==null) return;
         if(root.next==null){
             if(root.right!=null) root.right.next=null;
             if(root.left!=null) root.left.next=root.right;
         }else{
             TreeLinkNode p = root.next;
             TreeLinkNode q = null;
             while(p!=null){
                 if(p.left!=null) {q=p.left; break;}
                 if(p.right!=null) {q=p.right; break;}
                 p=p.next;
             }
             if(root.right!=null) root.right.next=q;
             if(root.left!=null&&root.right!=null) root.left.next=root.right;
             if(root.left!=null&&root.right==null) root.left.next=q;
         }
       
         dfs(root.right);
         dfs(root.left);
     }
}

09. Binary Tree Inorder Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
     
        if (root==null) return res;
     
        Stack<TreeNode> stack = new Stack<TreeNode> ();
        stack.push(root);
     
        TreeNode current = root.left;
     
        while (!stack.isEmpty() || current!=null) {
            if (current!=null) {
                stack.push(current);
                current = current.left;
            } else {
                current = stack.peek();
                res.add(current.val);
                stack.pop();
                current = current.right;
            }
        }
     
        return res;
    }
}


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        inorder(root, res);
        return res;
    }
   
    public void inorder(TreeNode root, ArrayList<Integer> res) {
        if (root==null) return;
       
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}