Path Sum II | Leetcode

Given a binary tree and a sum, find all root-to-leaf paths where each path's 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]
]

---

Solution: Maintain a current list of node values as you are recursing down each path. Subtract the node's value from sum each time. When you reach a leaf node (node.left == node.right == null), check if the sum is 0. If it were 0, add it to the list of answers.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) return answer;
        pathSum(answer, new ArrayList<Integer>(), root, sum);
        return answer;
    }
    
    private void pathSum(List<List<Integer>> answer, List<Integer> list, TreeNode node, int sum) {
        sum -= node.val;
        list.add(node.val);
        if (node.left == null && node.right == null) {
            if (sum == 0) answer.add(new ArrayList<Integer>(list));
        } else {
            if (node.left != null) pathSum(answer, list, node.left, sum);
            if (node.right != null) pathSum(answer, list, node.right, sum);
        }
        list.remove(list.size() - 1);
    }
}

Path Sum | Leetcode

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exists a root-to-leaf path 5->4->11->2 for which the sum is 22.

---

Solution: When the root node is null, return false (even when sum is 0). Recurse down the tree until you find a leaf node. For each recursion, subtract the value of the current node from sum. When we get to a leaf node, if the sum is 0, then return true.

/**
 * Definition for a binary tree node.
 * 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;
        return recurse(root, sum);
    }
    
    private boolean recurse(TreeNode node, int sum) {
        sum -= node.val;
        if (node.left == null && node.right == null) return (sum == 0);
        if (node.left != null && recurse(node.left, sum)) return true;
        if (node.right != null && recurse(node.right, sum)) return true;
        return false;
    }
}

Minimum Depth of Binary Tree | Leetcode

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

---

Solution: A tricky question. The minimum depth in this question must be traced down to a leaf node. For the non-leaf node, we will never take its depth as the answer.

For example, this tree has a minimum depth of 3 even though the 2 has no right child, which normally gives a minimum depth of 2.

             1
            / \
           2   3
          /     \
         4       5

For the algorithm, we ignore the missing left or right child if the other child (its sibling) is present.

/**
 * Definition for a binary tree node.
 * 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;
        if (root.left == null) return 1 + minDepth(root.right);
        if (root.right == null) return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

Balanced Binary Tree | Leetcode

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

---

Solution: This is a trick question. We are not trying to find out if the tree is height-balanced or not. We are trying to see if each of the left and right sub-trees are height-balanced or not.

For example, the tree [1,2,2,3,null,null,3,4,null,null,4] is not height-balanced by the definition in this question, even though it looks height-balanced.

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

Therefore we just need to check height-balanced for each of the left and right children pairs.

/**
 * Definition for a binary tree node.
 * 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);
    }
    
    public int maxDepth(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}

Convert Sorted List to Binary Search Tree | Leetcode

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

---

Solution: First find the length of the linked list. Then form the tree bottom up by going node by node in the linked list. Check for the end condition using the start and end indexes. Form the left child sub-tree first. Take the root node. Then form the right child sub-tree.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ListNode list;
    
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        int length = 0;
        for (ListNode tmp = head; tmp != null; tmp = tmp.next, length++);
        list = head;
        return sortedListToBST(0, length - 1);
    }
    
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode left = sortedListToBST(start, mid - 1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = left;
        list = list.next;
        parent.right = sortedListToBST(mid + 1, end);
        return parent;
    }
}

Convert Sorted Array to Binary Search Tree | Leetcode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

---

Solution: Take the middle element as the root node. Recurse on left and right sub-arrays and put as children nodes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int i, int j) {
        if (i > j) return null;
        int mid = i + (j - i) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, i, mid - 1);
        node.right = sortedArrayToBST(nums, mid + 1, j);
        return node;
    }
}

Binary Tree Level Order Traversal II | Leetcode

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

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

---

Solution: Add each level of nodes as a list. Collect all the children nodes first. Then collect the integer values as a list. Add this list to the front of the answer list.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> answer = new LinkedList<>();
        if (root == null) return answer;
        List<TreeNode> nodes = new ArrayList<>();
        List<TreeNode> children = new ArrayList<>();
        nodes.add(root);
        do {
            List<Integer> list = new ArrayList<>();
            for (TreeNode node: nodes) {
                list.add(node.val);
                if (node.left != null) children.add(node.left);
                if (node.right != null) children.add(node.right);
            }
            answer.addFirst(list);
            nodes.clear();
            List<TreeNode> tmp = nodes;
            nodes = children;
            children = tmp;
        } while (!nodes.isEmpty());
        return answer;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal | Leetcode

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

Note:
You may assume that duplicates do not exist in the tree.

---

Solution: In each recursion, the last element in the postorder is always the root node. Find the root node in the inorder. Put everything on the left of the root node in the left sub-tree, and everything on the right of the root node in the right sub-tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private final Map<Integer, Integer> inOrderIndex = new HashMap<>();
    private int postOrderIndex;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++) {
            inOrderIndex.put(inorder[i], i);
        }
        postOrderIndex = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int[] postorder, int i0, int i1) {
        if (i0 > i1) return null;
        TreeNode root = new TreeNode(postorder[postOrderIndex--]);
        int rootIndex = inOrderIndex.get(root.val);
        root.right = buildTree(inorder, postorder, rootIndex + 1, i1);
        root.left = buildTree(inorder, postorder, i0, rootIndex - 1);
        return root;
    }
}

Construct Binary Tree from Preorder and Inorder Traversal | Leetcode

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

Note:
You may assume that duplicates do not exist in the tree.

---

Solution: The first node in the preorder is always the root node. Find this same node in the inorder. All the nodes to the left belong to the left sub-tree. All the nodes to the right belong to the right sub-tree. In each recursion, always pick the next node from the preorder as the root node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private final Map<Integer, Integer> inOrderIndexMap = new HashMap<>();
    private int preOrderIndex = 0;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++) {
            inOrderIndexMap.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTree(int[] preorder, int[] inorder, int i0, int i1) {
        if (i0 > i1) return null;
        TreeNode root = new TreeNode(preorder[preOrderIndex++]);
        int rootIndex = inOrderIndexMap.get(root.val);
        root.left = buildTree(preorder, inorder, i0, rootIndex - 1);
        root.right = buildTree(preorder, inorder, rootIndex + 1, i1);
        return root;
    }
}

Maximum Depth of Binary Tree | Leetcode

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

---

Solution: Recurse down the tree, and return the maximum of the depth of the left and right sub-trees.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        return maxDepth(root, 0);
    }
    
    private int maxDepth(TreeNode node, int depth) {
        if (node == null) return depth;
        return Math.max(maxDepth(node.left, depth + 1), maxDepth(node.right, depth + 1));
    }
}

Binary Tree Zigzag Level Order Traversal | Leetcode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

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

---

Solution: Maintain two lists so that we can choose whether to add the nodes from first to last (for odd rows) or from last to first (for even rows). In each top-level loop, add all the children of the current level nodes.

There are several slightly different ways to solve this problem. The algorithm I show here keeps a direction boolean "leftToRight", and swaps the two lists (curList and nextList) for the next iteration.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        if (root == null) return answer;
        
        List curList = new ArrayList<>();
        List nextList = new ArrayList<>();
        curList.add(root);
        boolean leftToRight = true;
        
        do {
            List<Integer> list = new ArrayList<>();
            answer.add(list);
            
            if (leftToRight) {
                for (int i = 0; i < curList.size(); i++) {
                    list.add(curList.get(i).val);
                }
            } else {
                for (int i = curList.size() - 1; i >= 0; i--) {
                    list.add(curList.get(i).val);
                }
            }
            
            leftToRight = !leftToRight;
            
            for (TreeNode node: curList) {
                if (node.left != null) nextList.add(node.left);
                if (node.right != null) nextList.add(node.right);
            }
            curList.clear();
            
            List<TreeNode> tmp = curList;
            curList = nextList;
            nextList = tmp;
        } while (!curList.isEmpty());
        
        return answer;
    }
}

Binary Tree Level Order Traversal | Leetcode

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

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

---

Solution: Maintain a list of list as the answer. Traverse in pre-order with the depth information. For each node of depth D, add it to the list with index D, where D=0 for the root node.

It does not matter if you traverse pre-order, in-order, or post-order. The result will be the same for any traversal order.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> answer = new ArrayList<>();
        traverse(answer, root, 0);
        return answer;
    }
    
    private void traverse(List<List<Integer>> answer, TreeNode node, int depth) {
        if (node == null) return;
        while (answer.size() <= depth) answer.add(new ArrayList<Integer>());
        answer.get(depth).add(node.val);
        traverse(answer, node.left, depth + 1);
        traverse(answer, node.right, depth + 1);
    }
}

Symmetric Tree | Leetcode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

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

---

Solution: Recurse check for equality, except that we compare the left.left child with the right.right child, and the right.left child with the left.right child.

Algorithm 1: Recursive (easier)

/**
 * Definition for a binary tree node.
 * 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 left, TreeNode right) {
        if (left == right) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right);
    }
}

Algorithm 2: Iterative (harder)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static class TreeNodePair {
        private TreeNode node1;
        private TreeNode node2;
        
        private TreeNodePair(TreeNode node1, TreeNode node2) {
            this.node1 = node1;
            this.node2 = node2;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack stack = new Stack<>();
        stack.add(new TreeNodePair(root.left, root.right));
        do {
            TreeNodePair pair = stack.pop();
            if (pair.node1 == pair.node2) continue;
            if (pair.node1 == null || pair.node2 == null) return false;
            if (pair.node1.val != pair.node2.val) return false;
            stack.add(new TreeNodePair(pair.node1.left, pair.node2.right));
            stack.add(new TreeNodePair(pair.node2.left, pair.node1.right));
        } while (!stack.isEmpty());
        return true;
    }
}

Same Tree | Leetcode

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

---

Solution: Check the current node, and then recurse using the same function for both the left and right children.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Recover Binary Search Tree | Leetcode

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

Recover the tree without changing its structure.
 
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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

---

Solution: Do in-order traversal and find two nodes that are out-of-order. After the traversal is done, swap the two nodes. I would not think this algorithm is "straight forward". This uses O(log n) space in the stack which is not the right answer.

The right answer is to use Morris Traversal, which uses O(1) space, but I am not sure how anyone can come up with the algorithm in a short time. (http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/)

Algorithm 1: Recursion

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode outOfOrderNode1;
    private TreeNode outOfOrderNode2;
    private TreeNode prevNode;

    public void recoverTree(TreeNode root) {
        findNodesInOrder(root);
        
        // Cheap swap possible in Leetcode.
        // In real life, probably need both parent nodes to do swap.
        int tmp = outOfOrderNode1.val;
        outOfOrderNode1.val = outOfOrderNode2.val;
        outOfOrderNode2.val = tmp;
    }
    
    private void findNodesInOrder(TreeNode node) {
        if (node == null) return;
        findNodesInOrder(node.left);
        
        if (prevNode != null && prevNode.val >= node.val) {
            // Both the previous node and the current node are out-of-order.
            if (outOfOrderNode1 == null) {
                outOfOrderNode1 = prevNode;
            }
            outOfOrderNode2 = node;
        }
        prevNode = node;
        
        findNodesInOrder(node.right);
    }
}

Algorithm 2: Morris Traversal

public class Solution {
    private TreeNode curNode;
    private TreeNode prevNode;
    private TreeNode outOfOrderNode1;
    private TreeNode outOfOrderNode2;

    public void recoverTree(TreeNode root) {
        curNode = root;
        
        while (curNode != null) {
            if (curNode.left == null) {
                checkUpdateOutOfOrderNodes();
                curNode = curNode.right;
                continue;
            }
            
            TreeNode node = curNode.left;
            while (node.right != null && node.right != curNode) {
                node = node.right;
            }
            if (node.right == null) {
                node.right = curNode;
                curNode = curNode.left;
            } else {
                node.right = null;
                checkUpdateOutOfOrderNodes();
                curNode = curNode.right;
            }
        }
        
        int tmp = outOfOrderNode1.val;
        outOfOrderNode1.val = outOfOrderNode2.val;
        outOfOrderNode2.val = tmp;
    }
    
    private void checkUpdateOutOfOrderNodes() {
        if (prevNode != null && prevNode.val >= curNode.val) {
            if (outOfOrderNode1 == null) {
                outOfOrderNode1 = prevNode;
            }
            outOfOrderNode2 = curNode;
        }
        prevNode = curNode;
    }
}

Validate Binary Search Tree | Leetcode

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.

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

---

Solution: Drill down the tree into the left and right children. For each drill down, add a boundary condition, either left or right bound. For the left child, add the right bound of the parent node's value. For the right child, add the left bound of the parent node's value.

Algorithm 1: Recursive (Simpler, but bounded by stack memory)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode node, Integer leftBound, Integer rightBound) {
        if (node == null) return true;
        if (leftBound != null && node.val <= leftBound) return false;
        if (rightBound != null && node.val >= rightBound) return false;
        return isValidBST(node.left, leftBound, node.val)
                && isValidBST(node.right, node.val, rightBound);
    }
}

Algorithm 2: Iterative (More verbose, but not bounded by stack memory)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static class BoundedNode {
        private TreeNode node;
        private Integer leftBound;
        private Integer rightBound;
        
        private BoundedNode(TreeNode node, Integer leftBound, Integer rightBound) {
            this.node = node;
            this.leftBound = leftBound;
            this.rightBound = rightBound;
        }
    }
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        
        // Using stack or queue does not matter.
        Stack<BoundedNode> stack = new Stack<>();
        stack.push(new BoundedNode(root, null, null));
        
        do {
            BoundedNode b = stack.pop();
            if (b.leftBound != null && b.node.val <= b.leftBound) return false;
            if (b.rightBound != null && b.node.val >= b.rightBound) return false;
            if (b.node.left != null) {
                stack.push(new BoundedNode(b.node.left, b.leftBound, b.node.val));
            }
            if (b.node.right != null) {
                stack.push(new BoundedNode(b.node.right, b.node.val, b.rightBound));
            }
        } while (!stack.isEmpty());
        
        return true;
    }
}

Interleaving String | Leetcode

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.

---

Solution: This is a good practice problem for 2D dynamic programming.

First check the lengths of the strings to make sure they match before we start doing anything.

For the algorithm and formula, it is probably better to read the code directly.

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

        for (int i = 0; i < s2.length() && s2.charAt(i) == s3.charAt(i); i++) {
            m[0][i + 1] = true;
        }
        
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                m[i + 1][j + 1] =
                        (m[i][j + 1] && s1.charAt(i) == s3.charAt(i + j + 1)) ||
                        (m[i + 1][j] && s2.charAt(j) == s3.charAt(i + j + 1));
            }
        }
        return m[s1.length()][s2.length()];
    }
}

Unique Binary Search Trees | Leetcode

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

---

Solution: When n is 0, the answer is 1 (a null tree), not 0. When n is 1, the answer is also 1. n=0 and n=1 form the base cases.

For the rest of the trees, we iterate i from 1 to n, and then for each i, we count how many unique trees we can form. The number of unique trees is the number of unique trees on the left side multiply by the number of unique trees on the right side.

The caching part is just to make the code complete faster.

We could have used an array of n elements as the cache, given that we are always going to lookup from 2 to n only, but using a hashmap is more generic and makes the code shorter and simpler to follow.

public class Solution {
    private static final Map<Integer, Integer> cache = new HashMap<>();
    
    public int numTrees(int n) {
        if (n <= 1) return 1;
        if (cache.containsKey(n)) return cache.get(n);
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += numTrees(i - 1) * numTrees(n - i);
        }
        cache.put(n, count);
        return count;
    }
}

Unique Binary Search Trees II | Leetcode

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.

---

Solution: Iterate i from 1 to n, form new trees with node i as the root each time. In each recursion, always create a new list of trees. Then plug this list into the caller to get the answer.

When we try to generate an empty tree, it is important to set the tree as a null node, instead of not adding it as an answer. This is because this will simplify the logic when we set the left and right children of the parent node as null directly from the returned answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }
    
    private List<TreeNode> generateTrees(int first, int last) {
        List<TreeNode> answer = new ArrayList<>();
        if (first > last) {
            answer.add(null);
            return answer;
        }        
        for (int i = first; i <= last; i++) {
            List<TreeNode> leftTrees = generateTrees(first, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, last);
            
            for (TreeNode leftTree: leftTrees) {
                for (TreeNode rightTree: rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    answer.add(root);
                }
            }
        }
        return answer;
    }
}

Binary Tree Inorder Traversal | Leetcode

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

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

---

Solution: In-order traversal is to go left first, then take self, then go right. The trick here is to use a stack to simulate recursion. Besides that, we also need a current node that can help us to cleanly process off the nodes that we pop off the stack. Whatever we pop off the stack, we cannot push it back. If we do that we will get into an infinite loop.

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

Restore IP Addresses | Leetcode

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)

---

Solution: Use a recursive combinatorial algorithm. Whenever the last added character was not a dot, add a dot. Whenever the last added character was zero, and the current number is zero, then return because we cannot have anything after a leading zero. For numbers, add it only if it will keep the current number less than or equal to 255.

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        restore(list, sb, s, 0, 0, 0);
        return list;
    }
    
    private void restore(List<String> list, StringBuilder sb, String s, int index, int word, int curNum) {
        if (index == s.length() && word == 3 && sb.charAt(sb.length() - 1) != '.') {
            list.add(sb.toString());
        }
        if (index >= s.length() || word > 3) {
            return;
        }

        if (sb.length() > 0) {
            int prev = sb.charAt(sb.length() - 1);
            // Add dot whenever possible.
            if (prev != '.') {
                sb.append('.');
                restore(list, sb, s, index, word + 1, 0);
                sb.setLength(sb.length() - 1);
            }
            // If last digit was already zero, then cannot double-up on zeros.
            if (curNum == 0 && prev == '0') {
                return;
            }
        }

        // Add next digit to current number if within range.
        int ch = s.charAt(index);
        curNum = (curNum * 10) + (ch - '0');
        if (curNum <= 255) {
            sb.append((char) ch);
            restore(list, sb, s, index + 1, word, curNum);
            sb.setLength(sb.length() - 1);
        }
    }
}

Reverse Linked List II | Leetcode

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.

---

Solution: This is a tricky linked list question that is hard to get right the first time. The idea is quite straightforward. First, skip the first (m - 1) nodes so that you can get to one node before m. If m is the head node, then the node before head is called "beforeHead", which is an artificial node to simplify our algorithm.

Second, from the m-th node to the n-th node, reverse the list in-place.

Lastly, when the reversal is done, link up the whole list. You will need to join the node before m to the n-th node, and the m-th node to the node after n.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m == n) return head;
        
        // Avoid needing to keep track of head node later on.
        ListNode beforeHead = new ListNode(0);
        beforeHead.next = head;
        
        // Skip first m-1 nodes to get to one node before m.
        ListNode prev = beforeHead;
        for (int i = m - 1; i > 0; i--) {
            prev = prev.next;
        }
        
        // Reverse from nodes m to n in-place.
        ListNode beforeMthNode = prev;
        ListNode mthNode = prev.next;
        ListNode cur = mthNode;
        for (int i = n - m; i >= 0; i--) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        
        // Tie up loose ends.
        beforeMthNode.next = prev; // prev is the (n-1)-th node
        mthNode.next = cur;        // cur is the n-th node
        
        return beforeHead.next;
    }
}

Decode Ways | Leetcode

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

---

Solution: Use the dynamic programming formula f[i] = f[i - 1] + f[i - 2] (f is given as "ways" in the code). But it is not straightforward. You can add f[i - 1] only if the current digit is a valid standalone code (0..9), else you cannot add f[i - 1]. You can add f[i - 2] only if the previous digit (i - 1) and the current digit forms a valid code (10..26), else you cannot add f[i - 2]. We start from 10 (in 10..26) because if it starts from 0, then it will be accounted for by f[i - 1]. Hence it cannot be double-counted.

Setting the first two counts f[0] and f[1] is not trivial. If f[0] is a standalone code (1..9), then we have at least 1 way, hence set f[0] = 1, else f[0] = 0. If f[0] and f[1] forms a standalone code (10..26), then we have at least 1 way, hence set f[1] = 1, else f[1] = 0. If both f[0] and f[1] are standalone codes (1..9), then we get one more way at position f[1], hence f[1]++.

From the base values f[0] and f[1], iterate through the string and apply the formula f[i] = f[i - 1] + f[i - 2] accordingly. The answer will be stored in the last element of f.

public class Solution {
    private boolean isValid(int ch) {
        // True if 1 <= num <= 9.
        return ch >= '1' && ch <= '9';
    }

    private boolean isValid(int ch1, int ch2) {
        // True if 10 <= num <= 26.
        return (ch1 == '1' && ch2 >= '0' && ch2 <= '9')
                || (ch1 == '2' && ch2 >= '0' && ch2 <= '6');
    }

    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        
        int[] ways = new int[s.length()];
        
        // Set ways[0].
        if (isValid(s.charAt(0))) ways[0]++;
        if (s.length() == 1) return ways[0];
        
        // Set ways[1].
        if (isValid(s.charAt(0)) && isValid(s.charAt(1))) ways[1]++;
        if (isValid(s.charAt(0), s.charAt(1))) ways[1]++;
        
        // ways[i] = ways[i - 1] + ways[i - 2] with checking.
        for (int i = 2; i < s.length(); i++) {
            if (isValid(s.charAt(i))) ways[i] = ways[i - 1];
            if (isValid(s.charAt(i - 1), s.charAt(i))) ways[i] += ways[i - 2];
        }
        
        return ways[s.length() - 1];
    }
}

Subsets II | Leetcode

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

---

Solution: Same algorithm as finding all subsets (combinations), except that we add a duplicate check. We do this by maintaining a Set of Strings. Each possible list in the combinations is conveniently converted to string using List.toString().

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        List<Integer> list = new ArrayList<>(nums.length);
        Arrays.sort(nums);
        subsetsWithDup(nums, answer, list, seen, 0);
        return answer;
    }
    
    private void subsetsWithDup(int[] nums, List<List<Integer>> answer,
            List<Integer> list, Set<String> seen, int start) {
        String s = list.toString();
        if (!seen.contains(s)) {
            answer.add(new ArrayList<Integer>(list));
            seen.add(s);
        }
        if (start == nums.length) return;
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsWithDup(nums, answer, list, seen, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

Gray Code | Leetcode

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.

---

Solution: Not a fun problem. See https://en.wikipedia.org/wiki/Gray_code.

public class Solution {
    private int binaryToGray(int n) {
        return (n >> 1) ^ n;
    }
    
    public List<Integer> grayCode(int n) {
        int max = (int) Math.pow(2, n);
        List<Integer> list = new ArrayList<>(max);
        for (int i = 0; i < max; i++) {
            list.add(binaryToGray(i));
        }
        return list;
    }
}

Merge Sorted Array | Leetcode

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
 
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

---

Solution: Basic merge algorithm of the merge sort. Main trick is to start filling in the answer from the back of the array. If you try to fill in the answer starting from the front, then you will either need to allocate a new array at the beginning, or push back all the existing elements in the arrays for every out-of-order element insert.

Maintain one pointer for each array to merge. When there is something left in both arrays, compare the values. When either one of the arrays is exhausted, just take elements from the non-empty array until done.

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m + n - 1; i >= 0; i--) {
            if (m <= 0) {
                nums1[i] = nums2[--n];
            } else if (n <= 0) {
                nums1[i] = nums1[--m];
            } else {
                if (nums1[m - 1] < nums2[n - 1]) {
                    nums1[i] = nums2[--n];
                } else {
                    nums1[i] = nums1[--m];
                }
            }
        }
    }
}

Scramble String | Leetcode

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

---

Solution: Iterate through the string and split each string into two parts. The first part consists of the first i characters of S1, and the second part the rest of S1. Try to match this with two parts from S2.

The first way to split S2 into two parts is to take the first i characters of S2, and then the rest of S2.

The second way to split S2 into two parts is to take the last (length - i) characters of S2, and then the first (length - i) characters of S2.

The code "if (s1.chars().sum() != s2.chars().sum()) return false;" is to check that if the characters in S1 and S2 are different, then they cannot be scrambles of each other. This line is needed only to improve the speed of the algorithm to beat leetcode's online judge. The check is not foolproof, but it is good enough to pass leetcode's test.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        if (s1.chars().sum() != s2.chars().sum()) return false;
        
        for (int i = 1; i < s1.length(); i++) {
            String left1 = s1.substring(0, i);
            String right1 = s1.substring(i);
            
            String left2 = s2.substring(0, i);
            String right2 = s2.substring(i);
            
            if (isScramble(left1, left2) && isScramble(right1, right2)) {
                return true;
            }
            
            int j = s2.length() - i;
            right2 = s2.substring(j);
            left2 = s2.substring(0, j);
            
            if (isScramble(left1, right2) && isScramble(right1, left2)) {
                return true;
            }
        }
        
        return false;
    }
}

Partition List | Leetcode

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

---

Solution: Iterate through the linked list from beginning to end. Maintain two new linked lists, left and right, and for each element in the given linked list, either append it to left or right. At the end, join left to right to form one single linked list as the answer.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode leftHead = null;
        ListNode left = null;
        ListNode rightHead = null;
        ListNode right = null;
        
        while (head != null) {
            if (head.val < x) {
                if (leftHead == null) {
                    leftHead = head;
                } else {
                    left.next = head;
                }
                left = head;
                head = head.next;
                left.next = null;
            } else {
                if (rightHead == null) {
                    rightHead = head;
                } else {
                    right.next = head;
                }
                right = head;
                head = head.next;
                right.next = null;
            }
        }
        
        if (left != null) {
            left.next = rightHead;
            return leftHead;
        }
        return rightHead;
    }
}

Maximal Rectangle | Leetcode

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

---

Solution: This is a very tricky one. You have to reuse the Largest Rectangle in Histogram algorithm in its entirety as part of the answer. This means that you have to be able to solve that problem before you can solve this one.

Build a matrix of histogram heights, where each row of the matrix can be treated as an independent histogram of heights. What is the "height" here? It is the number of contiguous 1's starting from this cell and going up all the way. For example:

Input:     Heights:
0 1 1 0    0 1 1 0
0 0 1 1    0 0 2 1
1 0 1 1    0 0 3 2

Apply the Largest Rectangle in Histogram algorithm on each row of the heights histogram. Then return the maximum area ever found.

Note: It should not matter whether you calculate the heights going upwards or going downwards.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        
        // Build matrix of heights of ones.
        int[][] heights = new int[matrix.length][matrix[0].length];
        for (int y = 0; y < matrix.length; y++) {
            for (int x = 0; x < matrix[0].length; x++) {
                int height = (matrix[y][x] == '1') ? 1 : 0;
                if (y > 0 && height > 0) height += heights[y - 1][x];
                heights[y][x] = height;
            }
        }
        
        // Use the largest rectangle in histogram algorithm on each row.
        Stack stack = new Stack<>();
        int maxArea = 0;
        for (int y = 0; y < matrix.length; y++) {
            stack.clear();
            maxArea = Math.max(findMaxArea(stack, heights[y]), maxArea);
        }
        return maxArea;
    }
    
    private int findMaxArea(Stack stack, int[] heights) {
        int maxArea = 0;
        int i = 0;
        do {
            while (!stack.isEmpty() && (i == heights.length || heights[i] < heights[stack.peek()])) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(height * width, maxArea);
            }
            stack.push(i++);
        } while (i <= heights.length);
        return maxArea;
    }
}

Largest Rectangle in Histogram | Leetcode

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.

---

Solution: This unfortunately is a hard to understand algorithm. I would not be able to know this algorithm without knowing it in advance.

The general idea is that we will keep a running stack. When the current bar is equal to or taller than the last bar in the stack, then we will push it into the stack. If not, we will try to exhaust down the stack until the stack is empty or the current bar in the stack is equal to or taller than the last bar in the stack.

For each time we exhaust the stack, we take out the top element. We take the height of this element to calculate the area of the rectangle. Then we try to get the width of the rectangle. When the stack is empty, we take the width as the index of the current bar, which is the width from the beginning until the bar right before the current bar. Else we take the width as "i - stack.peek() - 1", which is the width until the top element in the stack but excluding that top element.

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        
        do {
            // Exhaust the stack while the current bar is lower than the next one.
            while (!stack.isEmpty() && (i == height.length || height[i] < height[stack.peek()])) {
                // Get the height of the last bar.
                int h = height[stack.pop()];
                
                // Get the width of the current rectangle.
                // If the stack is empty, then we go back to the first bar.
                // Else we go back to the last bar higher than the current one.
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                
                maxArea = Math.max(h * width, maxArea);
            }
            stack.push(i++);
        } while (i <= height.length);
        
        return maxArea;
    }
}

Remove Duplicates from Sorted List | Leetcode

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

---

Solution: Iterate through the list. While the current node has the same value as the next node, remove the next node.

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

Remove Duplicates from Sorted List II | Leetcode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

---

Solution: One tricky bit about this question is that when the head element is a duplicate, we have to take care to return the correct value of head, which is not the same one we get from the argument. A convenient way to do this is to create a node "pre" coming before head, so that we will return pre.next no matter whether we remove head or not.

To know whether the elements are duplicates or not, we have to take the next two elements. But you cannot make an element remove itself. The only way to remove an element is to have a reference to the previous element. Hence we use the condition "cur.next.val == cur.next.next.val" instead of "cur.val == cur.next.val" to perform this check.

When there are duplicates, do not advance the current pointer. Otherwise, just advance to the next element.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        
        ListNode cur = pre;
        while (cur.next != null && cur.next.next != null) {
            // If the next two nodes have the same value,
            // then remove them all with the same value.
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                cur.next = cur.next.next.next;
                while (cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        
        return pre.next;
    }
}

Search in Rotated Sorted Array II | Leetcode

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.

---

Solution: Use a modified form of binary search. The key is that we cannot say for sure whether a portion of the array is sorted or not if the first number is equal to the last number, i.e. nums[lo] == nums[hi]. Therefore, we have to say that the first number must be less than the last number (i.e. nums[lo] < nums[hi]) before we are sure that it is sorted. When we are not sure the portion is sorted, just reuse binary search on each half of the array portion from lo to hi.

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

Remove Duplicates from Sorted Array II | Leetcode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

---

Solution: Keep an index of the last element that you want to keep as part of the de-duplicated array. Keep the last seen character and also the count of the number of times the same character has been seen. Traverse through the array, moving valid numbers to the index of the last valid element. When done iterating, the current index is the length of the new sub-array.

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int lastNum = nums[0];
        int lastIndex = 1;
        for (int i = 1, count = 1; i < nums.length; i++) {
            if (nums[i] == lastNum) {
                if (++count > 2) continue;
            } else {
                count = 1;
                lastNum = nums[i];
            }
            nums[lastIndex++] = lastNum;
        }
        return lastIndex;
    }
}

Word Search | Leetcode

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

---

Solution: Create a boolean matrix "seen" to mark whether each cell has been seen or not. A recursive function will then check for each character, checking the boolean matrix to avoid double-using each cell, and then self-recurse. When we reach the end of the word successfully, then we have found a match.

To reuse the board to mark seen is not a good idea because we do not have to restrict the possible range of input characters, unless this has otherwise been explicitly called out. Though you probably can reuse the board to pass the leetcode judge.

public class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] seen = new boolean[board.length][board[0].length];

        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                if (exists(board, seen, word, 0, y, x)) return true;
            }
        }
        return false;
    }
    
    private boolean exists(char[][] board, boolean[][] seen, String word, int start, int y, int x) {
        if (word.charAt(start) != board[y][x] || seen[y][x]) {
            return false;
        }
        
        if (start == word.length() - 1) return true;
        
        seen[y][x] = true;

        if (y > 0 && exists(board, seen, word, start + 1, y - 1, x)) {
            return true;
        }
        if (y < board.length - 1 && exists(board, seen, word, start + 1, y + 1, x)) {
            return true;
        }
        if (x > 0 && exists(board, seen, word, start + 1, y, x - 1)) {
            return true;
        }
        if (x < board[0].length - 1 && exists(board, seen, word, start + 1, y, x + 1)) {
            return true;
        }
        
        seen[y][x] = false;
        
        return false;
    }
}

Subsets | Leetcode

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

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

---

Solution: Sort the input array first. Initialize answer list. Then recurse starting from starting index 0. In each recursion, add given list as answer. Then loop through the input array starting from given index till the end. Collect each unique answer as you encounter them.

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();
        subsets(answer, new ArrayList<Integer>(nums.length), 0, nums);
        return answer;
    }
    
    private void subsets(List<List<Integer>> answer, List<Integer> list, int start, int[] nums) {
        answer.add(new ArrayList<Integer>(list));
        if (start >= nums.length) return;
        
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsets(answer, list, i + 1, nums);
            list.remove(list.size() - 1);
        }
    }
}

Combinations | Leetcode

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

---

Solution: First initialize the answer list before calling the recursive function. In the recursive function, put the termination condition first. When we have the list size == k, then we know this result is ripe for reaping. Save this result and then return. Otherwise, loop from the given starting index of this recursive call. In each loop, add the first character at the given starting index, call itself recursively, and then remove the added character. Doing so will let you collect all the C(n,k) combinations. But unfortunately it is a bit hard to explain why!

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

Minimum Window Substring | Leetcode

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.

---

Solution: Maintain a bag (multiset) of the characters in T. Iterate S from beginning to end. Keep a sliding window that goes from "windowStart" to the current index in S. Keep a counter for the number of remaining characters in T that we have not included in our sliding window yet. When the counter drops to zero, that means we have found a sliding window within S that contains all the characters in T.

There are some tricky things in this algorithm. First, the count of each element in the bag may become negative. For example, for a sliding window "ABBB", and T="AB", the count of B in the bag would be -2 and not 0! This means that you cannot use a real Bag data structure but you have to use a hashmap of integer to integer mapping.

Second, when we get a matching sliding window, try to collect the result immediately. But continue to shrink the sliding window from the left to the minimum length possible by advancing the windowStart pointer from the left. When you shrink the window until it no longer contains all the characters in T (remaining > 0), then stop shrinking the sliding window and continue iteration on S.

public class Solution {
    public String minWindow(String s, String t) {
        Map bag = new HashMap<>();
        for (int i = t.length() - 1; i >= 0; i--) {
            int ch = t.charAt(i);
            bag.put(ch, bag.containsKey(ch) ? bag.get(ch) + 1 : 1);
        }
        
        // Keep track of the minimum window found so far.        
        int minLength = 0;
        int minStart = 0;
        int minEnd = 0;
        int windowStart = 0;
        int remaining = t.length();

        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i);

            // Subtract ch from bag. Count could go negative!
            if (bag.containsKey(ch)) {
                if (bag.get(ch) > 0) remaining--;
                bag.put(ch, bag.get(ch) - 1);
            }
            
            while (remaining == 0 && windowStart <= i) {
                // Collect result if minimum.
                int len = i - windowStart + 1;
                if (minLength == 0 || len < minLength) {
                    minStart = windowStart;
                    minEnd = i;
                    minLength = len;
                }

                // Add back character if needed.
                ch = s.charAt(windowStart);
                if (bag.containsKey(ch)) {
                    if (bag.get(ch) >= 0) remaining++;
                    bag.put(ch, bag.get(ch) + 1);
                }

                // Advance windowStart pointer.
                windowStart++;
            }
        }
        
        return (minLength == 0) ? "" : s.substring(minStart, minEnd + 1);
    }
}

Sort Colors | Leetcode

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?

---

Solution: Keep the index of the last red (0) and the first blue (2). Start by iterating from the end of the array and filter out the blues. Then start iterating from the first element to the element before the index of the first blue we found so far. When we see a red, swap it with the first non-red element and increment the red pointer. When we see a blue, swap it with the last non-blue element and decrement the blue pointer. All the whites (1), if any, will remain in the middle of the array.

public class Solution {
    public void sortColors(int[] nums) {
        int blue = nums.length - 1;
        while (blue >= 0 && nums[blue] == 2) blue--;
        for (int i = 0, red = 0; i <= blue; i++) {
            if (nums[i] == 0) {
                if (i != red) {
                    int tmp = nums[red];
                    nums[red] = 0;
                    nums[i] = tmp;
                }
                red++;
            } else if (nums[i] == 2) {
                int tmp = nums[blue];
                nums[blue--] = 2;
                nums[i--] = tmp;
            }
        }
    }
}

Search a 2D Matrix | Leetcode

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

---

Solution: Pretend that the 2D matrix is one linear array. Given an index i in the linear array, you can calculate the position of the corresponding element in the matrix. The row and column is given by: row = (i / cols), column = (i % cols). Perform an ordinary binary search to get the answer.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int lo = 0;
        int hi = (rows * cols) - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int m = matrix[mid / cols][mid % cols];
            if (m == target) {
                return true;
            }
            if (m < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
}

Set Matrix Zeroes | Leetcode

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

 

Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

---

Solution: Use two booleans, one for first row, one for first column. Check if first row and first column is zero. Then check all other rows and columns to see if that row and column is zero. Mark all rows other than the first row. Mark all columns other than the first column. Mark the first row and first column as needed.

Algorithm 1: Use for loops

public class Solution {
    public void setZeroes(int[][] matrix) {
        int numRows = matrix.length;
        int numCols = matrix[0].length;
        boolean isFirstRowZero = false;
        boolean isFirstColZero = false;
        
        // Check if first row is zero.
        for (int col = 0; col < numCols; col++) {
            if (matrix[0][col] == 0) {
                isFirstRowZero = true;
                break;
            }
        }
        
        // Check if first column is zero.
        for (int row = 0; row < numRows; row++) {
            if (matrix[row][0] == 0) {
                isFirstColZero = true;
                break;
            }
        }
        
        // Check if each row/column is zero by marking zero in first column/row.
        for (int row = 1; row < numRows; row++) {
            for (int col = 1; col < numCols; col++) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }
        
        // Mark all rows except first.
        for (int row = 1; row < numRows; row++) {
            if (matrix[row][0] == 0) {
                for (int col = 1; col < numCols; col++) {
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Mark all columns except first.
        for (int col = 1; col < numCols; col++) {
            if (matrix[0][col] == 0) {
                for (int row = 1; row < numRows; row++) {
                    matrix[row][col] = 0;
                }
            }
        }

        // Mark first row.
        if (isFirstRowZero) {
            for (int col = 0; col < numCols; col++) {
                matrix[0][col] = 0;
            }
        }
        
        // Mark first column.
        if (isFirstColZero) {
            for (int row = 0; row < numRows; row++) {
                matrix[row][0] = 0;
            }
        }
    }
}

Algorithm 2: Use Java 8 streams

public class Solution {
    private int[][] matrix;
        
    public void setZeroes(int[][] matrix) {
        this.matrix = matrix;
        
        boolean isFirstRowZero = rowHasZero(0);
        boolean isFirstColZero = colHasZero(0);
        
        rows(1).filter(row -> rowHasZero(row)).forEach(row -> matrix[row][0] = 0);
        cols(1).filter(col -> colHasZero(col)).forEach(col -> matrix[0][col] = 0);
        
        rows(1).filter(row -> matrix[row][0] == 0).forEach(row -> setRowToZeros(row));
        cols(1).filter(col -> matrix[0][col] == 0).forEach(col -> setColToZeros(col));

        if (isFirstRowZero) setRowToZeros(0);
        if (isFirstColZero) setColToZeros(0);
    }
    
    private IntStream rows(int start) {
        return IntStream.range(start, matrix.length);
    }
    
    private IntStream cols(int start) {
        return IntStream.range(start, matrix[0].length);
    }
    
    private boolean rowHasZero(int row) {
        return cols(0).anyMatch(col -> matrix[row][col] == 0);
    }

    private boolean colHasZero(int col) {
        return rows(0).anyMatch(row -> matrix[row][col] == 0);
    }

    private void setRowToZeros(int row) {
        cols(0).forEach(col -> matrix[row][col] = 0);
    }
    
    private void setColToZeros(int col) {
        rows(0).forEach(row -> matrix[row][col] = 0);
    }
}

Edit Distance | Leetcode

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

---

Solution: The only thing that works is dynamic programming on a 2D matrix. Great details available on wikipedia: https://en.wikipedia.org/wiki/Levenshtein_distance

Defining the edit distance function f(y,x):
For 1 <= y <= len(word1) and 1 <= x <= len(word2):

   f(y, x) = minimum {
                         f(y-1, x) + 1,
                         f(y, x-1) + 1,
                         f(y-1, x-1) + (word1[y] == word2[x] ? 0 : 1)
                     }

OR

   f(y, x) = minimum of:
                         DELETE_COST
                         INSERT_COST
                         (word1[y] == word2[x] ? NO_OP_COST : REPLACE_COST)

There are two different ways to implement the same algorithm:
1. Use a len1 x len2 matrix.
2. Use two arrays of the same length, either len1 or len2, depending on the direction of iteration.

The first algorithm is more straightforward to implement. The second algorithm is a space optimization of the first algorithm, and thus is a little more complex than the first algorithm. But the idea is identical in both cases. You probably should use the first algorithm in normal interview cases, but be prepared to also use the second algorithm if you do too well and the interviewer wants you to optimize for space. :-)

Algorithm 1: O(N^2) space

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1 == 0) return len2;
        if (len2 == 0) return len1;
        
        // For all y and x, m[y,x] will hold the edit distance between
        // the first y characters of word1 and the first x characters of word2.
        // Note that m has (len1 + 1) * (len2 + 1) values.
        int[][] m = new int[len1 + 1][];
        for (int y = 0; y <= len1; y++) {
            m[y] = new int[len2 + 1];
        }
        
        // Cost of dropping all characters from word1.
        // Note: we must include m[len1][0] also.
        for (int y = 1; y <= len1; y++) {
            m[y][0] = y;
        }
        
        // Cost of inserting all characters from word2.
        // Note: we must include m[0][len2] also.
        for (int x = 1; x <= len2; x++) {
            m[0][x] = x;
        }
        
        for (int y = 1; y <= len1; y++) {
            int char1 = word1.charAt(y - 1);

            for (int x = 1; x <= len2; x++) {
                int char2 = word2.charAt(x - 1);

                int leftCostPlusInsert = m[y][x - 1] + 1;
                int topCostPlusDelete = m[y - 1][x] + 1;
                int minCost = Math.min(leftCostPlusInsert, topCostPlusDelete);
                int replacementCostIfAny = (char1 == char2) ? 0 : 1;

                m[y][x] = Math.min(minCost, m[y - 1][x - 1] + replacementCostIfAny);
            }
        }
        
        return m[len1][len2];
    }
}

Algorithm 2: O(N) space

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1 == 0) return len2;
        if (len2 == 0) return len1;
        
        int[] a1 = new int[len2 + 1];
        int[] a2 = new int[len2 + 1];
        
        for (int x = 1; x <= len2; x++) {
            a1[x] = x;
        }

        for (int y = 1; y <= len1; y++) {
            a2[0] = y;
            int char1 = word1.charAt(y - 1);

            for (int x = 1; x <= len2; x++) {
                int char2 = word2.charAt(x - 1);

                int leftCostPlusInsert = a2[x - 1] + 1;
                int topCostPlusDelete = a1[x] + 1;
                int minCost = Math.min(leftCostPlusInsert, topCostPlusDelete);
                int replacementCostIfAny = (char1 == char2) ? 0 : 1;

                a2[x] = Math.min(minCost, a1[x - 1] + replacementCostIfAny);
            }
            
            // Swap a1 and a2.
            int[] tmp = a1;
            a1 = a2;
            a2 = tmp;
        }
        
        return a1[len2];
    }
}

Two Sum | Leetcode

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

Solution: Store index of each sub-target number in the array into a hashmap. The sub-target number is equal to target - nums[i]. When we see a number that is equal to the sub-target number later, then return the answer. Note that the index is 1-based for this question.

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map subTargetToIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            if (subTargetToIndex.containsKey(n)) {
                return new int[] { subTargetToIndex.get(n), i + 1 };
            }
            subTargetToIndex.put(target - n, i + 1);
        }
        return null;
    }
}

Home

List of Leetcode's problems and solutions:

#	Title	Acceptance	Difficulty	Status
256	Paint House	38.8%	Medium
255	Verify Preorder Sequence in Binary Search Tree	27.5%	Medium
254	Factor Combinations	29.5%	Medium
253	Meeting Rooms II	26.4%	Medium
252	Meeting Rooms	34.0%	Easy
251	Flatten 2D Vector	25.6%	Medium
250	Count Univalue Subtrees	33.6%	Medium
249	Group Shifted Strings	23.0%	Easy
248	Strobogrammatic Number III	21.1%	Hard
247	Strobogrammatic Number II	22.4%	Medium
246	Strobogrammatic Number	31.1%	Easy
245	Shortest Word Distance III	41.2%	Medium
244	Shortest Word Distance II	33.2%	Medium
243	Shortest Word Distance	39.1%	Easy
242	Valid Anagram	34.0%	Easy
241	Different Ways to Add Parentheses	26.0%	Medium
240	Search a 2D Matrix II	28.1%	Medium
239	Sliding Window Maximum	22.2%	Hard
238	Product of Array Except Self	34.6%	Medium
237	Delete Node in a Linked List	44.7%	Easy
236	Lowest Common Ancestor of a Binary Tree	26.6%	Medium
235	Lowest Common Ancestor of a Binary Search Tree	37.4%	Easy
234	Palindrome Linked List	21.7%	Easy
233	Number of Digit One	19.9%	Medium
232	Implement Queue using Stacks	33.8%	Easy
231	Power of Two	29.8%	Easy
230	Kth Smallest Element in a BST	29.7%	Medium
229	Majority Element II	22.1%	Medium
228	Summary Ranges	18.6%	Easy
227	Basic Calculator II	18.6%	Medium
226	Invert Binary Tree	37.1%	Easy
225	Implement Stack using Queues	30.4%	Easy
224	Basic Calculator	16.6%	Medium
223	Rectangle Area	25.7%	Easy
222	Count Complete Tree Nodes	20.5%	Medium
221	Maximal Square	19.7%	Medium
220	Contains Duplicate III	15.5%	Medium
219	Contains Duplicate II	25.6%	Easy
218	The Skyline Problem	16.5%	Hard
217	Contains Duplicate	36.0%	Easy
216	Combination Sum III	28.7%	Medium
215	Kth Largest Element in an Array	27.3%	Medium
214	Shortest Palindrome	16.1%	Hard
213	House Robber II	26.6%	Medium
212	Word Search II	14.8%	Hard
211	Add and Search Word - Data structure design	20.3%	Medium
210	Course Schedule II	19.5%	Medium
209	Minimum Size Subarray Sum	23.2%	Medium
208	Implement Trie (Prefix Tree)	24.8%	Medium
207	Course Schedule	22.1%	Medium
206	Reverse Linked List	32.3%	Easy
205	Isomorphic Strings	24.6%	Easy
204	Count Primes	19.8%	Easy
203	Remove Linked List Elements	25.5%	Easy
202	Happy Number	31.8%	Easy
201	Bitwise AND of Numbers Range	25.1%	Medium
200	Number of Islands	22.6%	Medium
199	Binary Tree Right Side View	27.8%	Medium
198	House Robber	29.3%	Easy
191	Number of 1 Bits	37.9%	Easy
190	Reverse Bits	28.7%	Easy
189	Rotate Array	18.1%	Easy
188	Best Time to Buy and Sell Stock IV	18.4%	Hard
187	Repeated DNA Sequences	20.3%	Medium
186	Reverse Words in a String II	31.6%	Medium
179	Largest Number	16.1%	Medium
174	Dungeon Game	18.1%	Hard
173	Binary Search Tree Iterator	29.6%	Medium
172	Factorial Trailing Zeroes	29.1%	Easy
171	Excel Sheet Column Number	36.6%	Easy
170	Two Sum III - Data structure design	25.0%	Easy
169	Majority Element	35.5%	Easy
168	Excel Sheet Column Title	18.3%	Easy
167	Two Sum II - Input array is sorted	43.3%	Medium
166	Fraction to Recurring Decimal	13.0%	Medium
165	Compare Version Numbers	15.3%	Easy
164	Maximum Gap	24.5%	Hard
163	Missing Ranges	24.3%	Medium
162	Find Peak Element	31.9%	Medium
161	One Edit Distance	24.5%	Medium
160	Intersection of Two Linked Lists	28.9%	Easy
159	Longest Substring with At Most Two Distinct Characters	30.6%	Hard
158	Read N Characters Given Read4 II - Call multiple times	22.6%	Hard
157	Read N Characters Given Read4	29.8%	Easy
156	Binary Tree Upside Down	34.2%	Medium
155	Min Stack	19.3%	Easy
154	Find Minimum in Rotated Sorted Array II	32.2%	Hard
153	Find Minimum in Rotated Sorted Array	33.5%	Medium
152	Maximum Product Subarray	19.6%	Medium
151	Reverse Words in a String	15.2%	Medium
150	Evaluate Reverse Polish Notation	21.4%	Medium
149	Max Points on a Line	12.8%	Hard
148	Sort List	22.3%	Medium
147	Insertion Sort List	26.7%	Medium
146	LRU Cache	15.1%	Hard
145	Binary Tree Postorder Traversal	32.6%	Hard
144	Binary Tree Preorder Traversal	36.3%	Medium
143	Reorder List	21.0%	Medium
142	Linked List Cycle II	31.4%	Medium
141	Linked List Cycle	36.4%	Medium
140	Word Break II	17.8%	Hard
139	Word Break	23.1%	Medium
138	Copy List with Random Pointer	25.4%	Hard
137	Single Number II	35.1%	Medium
136	Single Number	45.1%	Medium
135	Candy	20.7%	Hard
134	Gas Station	25.8%	Medium
133	Clone Graph	24.2%	Medium
132	Palindrome Partitioning II	19.9%	Hard
131	Palindrome Partitioning	27.0%	Medium
130	Surrounded Regions	14.8%	Medium
129	Sum Root to Leaf Numbers	30.3%	Medium
128	Longest Consecutive Sequence	29.6%	Hard
127	Word Ladder	19.4%	Medium
126	Word Ladder II	13.2%	Hard
125	Valid Palindrome	22.0%	Easy
124	Binary Tree Maximum Path Sum	21.6%	Hard
123	Best Time to Buy and Sell Stock III	24.0%	Hard
122	Best Time to Buy and Sell Stock II	38.5%	Medium
121	Best Time to Buy and Sell Stock	32.8%	Medium
120	Triangle	27.4%	Medium
119	Pascal's Triangle II	29.4%	Easy
118	Pascal's Triangle	30.1%	Easy
117	Populating Next Right Pointers in Each Node II	32.1%	Hard
116	Populating Next Right Pointers in Each Node	36.3%	Medium
115	Distinct Subsequences	26.6%	Hard
114	Flatten Binary Tree to Linked List	28.8%	Medium
113	Path Sum II	26.6%	Medium
112	Path Sum	29.6%	Easy
111	Minimum Depth of Binary Tree	28.9%	Easy
110	Balanced Binary Tree	31.9%	Easy
109	Convert Sorted List to Binary Search Tree	28.0%	Medium
108	Convert Sorted Array to Binary Search Tree	34.0%	Medium
107	Binary Tree Level Order Traversal II	31.0%	Easy
106	Construct Binary Tree from Inorder and Postorder Traversal	26.9%	Medium
105	Construct Binary Tree from Preorder and Inorder Traversal	26.4%	Medium
104	Maximum Depth of Binary Tree	45.1%	Easy
103	Binary Tree Zigzag Level Order Traversal	26.4%	Medium
102	Binary Tree Level Order Traversal	29.2%	Easy
101	Symmetric Tree	31.6%	Easy
100	Same Tree	41.4%	Easy
99	Recover Binary Search Tree	24.4%	Hard
98	Validate Binary Search Tree	20.3%	Medium
97	Interleaving String	20.8%	Hard
96	Unique Binary Search Trees	35.6%	Medium
95	Unique Binary Search Trees II	28.1%	Medium
94	Binary Tree Inorder Traversal	36.3%	Medium
93	Restore IP Addresses	21.1%	Medium
92	Reverse Linked List II	25.9%	Medium
91	Decode Ways	16.3%	Medium
90	Subsets II	27.8%	Medium
89	Gray Code	32.9%	Medium
88	Merge Sorted Array	29.1%	Easy
87	Scramble String	24.5%	Hard
86	Partition List	27.4%	Medium
85	Maximal Rectangle	22.1%	Hard
84	Largest Rectangle in Histogram	22.6%	Hard
83	Remove Duplicates from Sorted List	34.4%	Easy
82	Remove Duplicates from Sorted List II	25.0%	Medium
81	Search in Rotated Sorted Array II	31.2%	Medium
80	Remove Duplicates from Sorted Array II	30.4%	Medium
79	Word Search	20.5%	Medium
78	Subsets	28.2%	Medium
77	Combinations	31.0%	Medium
76	Minimum Window Substring	19.0%	Hard
75	Sort Colors	32.6%	Medium
74	Search a 2D Matrix	31.6%	Medium
73	Set Matrix Zeroes	31.5%	Medium
72	Edit Distance	26.4%	Hard
71	Simplify Path	20.1%	Medium
70	Climbing Stairs	34.4%	Easy
69	Sqrt(x)	23.2%	Medium
68	Text Justification	14.7%	Hard
67	Add Binary	24.6%	Easy
66	Plus One	30.3%	Easy
65	Valid Number	11.5%	Hard
64	Minimum Path Sum	32.3%	Medium
63	Unique Paths II	27.9%	Medium
62	Unique Paths	33.0%	Medium
61	Rotate List	21.6%	Medium
60	Permutation Sequence	22.8%	Medium
59	Spiral Matrix II	31.8%	Medium
58	Length of Last Word	27.6%	Easy
57	Insert Interval	21.6%	Hard
56	Merge Intervals	22.5%	Hard
55	Jump Game	26.9%	Medium
54	Spiral Matrix	20.8%	Medium
53	Maximum Subarray	34.4%	Medium
52	N-Queens II	36.1%	Hard
51	N-Queens	26.4%	Hard
50	Pow(x, n)	26.7%	Medium
49	Group Anagrams	24.3%	Medium
48	Rotate Image	32.0%	Medium
47	Permutations II	25.8%	Hard
46	Permutations	31.9%	Medium
45	Jump Game II	24.1%	Hard
44	Wildcard Matching	15.3%	Hard
43	Multiply Strings	21.1%	Medium
42	Trapping Rain Water	30.1%	Hard
41	First Missing Positive	22.8%	Hard
40	Combination Sum II	25.2%	Medium
39	Combination Sum	28.0%	Medium
38	Count and Say	25.3%	Easy
37	Sudoku Solver	22.1%	Hard
36	Valid Sudoku	27.2%	Easy
35	Search Insert Position	35.4%	Medium
34	Search for a Range	27.4%	Medium
33	Search in Rotated Sorted Array	28.7%	Hard
32	Longest Valid Parentheses	20.9%	Hard
31	Next Permutation	24.9%	Medium
30	Substring with Concatenation of All Words	19.6%	Hard
29	Divide Two Integers	14.9%	Medium
28	Implement strStr()	22.4%	Easy
27	Remove Element	31.8%	Easy
26	Remove Duplicates from Sorted Array	31.0%	Easy
25	Reverse Nodes in k-Group	25.3%	Hard
24	Swap Nodes in Pairs	32.3%	Medium
23	Merge k Sorted Lists	21.0%	Hard
22	Generate Parentheses	32.6%	Medium
21	Merge Two Sorted Lists	32.5%	Easy
20	Valid Parentheses	26.5%	Easy
19	Remove Nth Node From End of List	26.9%	Easy
18	4Sum	21.7%	Medium
17	Letter Combinations of a Phone Number	25.6%	Medium
16	3Sum Closest	26.8%	Medium
15	3Sum	16.9%	Medium
14	Longest Common Prefix	25.5%	Easy
13	Roman to Integer	34.3%	Easy
12	Integer to Roman	34.0%	Medium
11	Container With Most Water	31.8%	Medium
10	Regular Expression Matching	20.7%	Hard
9	Palindrome Number	28.4%	Easy
8	String to Integer (atoi)	12.8%	Easy
7	Reverse Integer	24.0%	Easy
6	ZigZag Conversion	21.5%	Easy
5	Longest Palindromic Substring	20.7%	Medium
4	Median of Two Sorted Arrays	17.1%	Hard
3	Longest Substring Without Repeating Characters	20.3%	Medium
2	Add Two Numbers	20.4%	Medium
1	Two Sum	17.7%	Medium