Max Points on a Line | Leetcode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

---

Solution: For each pair of points (O(N²)), first check whether they are the same point or not. If not, calculate the slope of the line passing through both of them. Keep count of the number of times each slope appears. The number of points on the same line for point X is the total of points which are identical to X (including point X itself) plus the maximum number of points having the same slope with a line passing through X. Since all these lines will pass through X, having the same slope will mean that they are the same line.

Keep track of the maximum count for each point of origin X and return the maximum count among all points as the answer.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length == 0) return 0;
        
        // At least one point will be on the same line as itself.
        int max = 1;
        
        // Using Double as the key is not ideal for double equality comparison,
        // but it works well enough to pass the Leetcode submission.
        // If we want to use approximate double comparison, we can use a loop
        // in the slope lookup logic to find a matching slope if it exists.
        Map<Double, Integer> slopeCount = new HashMap<>();
        
        for (int i = points.length - 1; i >= 1; i--) {
            int x1 = points[i].x;
            int y1 = points[i].y;
            
            int sameCount = 1; // add points[i] itself
            int verticalCount = 0;
            int horizontalCount = 0;
            int thisSlopeMax = 0;
            
            for (int j = i - 1; j >= 0; j--) {
                int x2 = points[j].x;
                int y2 = points[j].y;
                
                if (x1 == x2 && y1 == y2) {
                    sameCount++;
                } else if (x1 == x2) {
                    verticalCount++;
                } else if (y1 == y2) {
                    // By right not needed, but Java will consider 0.0 != -0.0,
                    // hence it is safer to just avoid this problem altogether.
                    horizontalCount++;
                } else {
                    double slope = ((double) (y1 - y2)) / ((double) (x1 - x2));
                    Integer oldSlopeCount = slopeCount.get(slope);
                    int newSlopeCount = (oldSlopeCount == null) ? 1 : oldSlopeCount + 1;
                    slopeCount.put(slope, newSlopeCount);
                    
                    thisSlopeMax = Math.max(thisSlopeMax, newSlopeCount);
                }
            }
            
            thisSlopeMax = Math.max(thisSlopeMax, Math.max(verticalCount, horizontalCount));
            max = Math.max(max, sameCount + thisSlopeMax);
            
            slopeCount.clear();
        }
        
        return max;
    }
}

Sort List | Leetcode

Sort a linked list in O(n log n) time using constant space complexity.

---

Solution: Probably the only way to do this using constant memory is to use merge sort. We use the technique of finding the middle of the linked list using a slow pointer and a fast pointer. So we can break down a linked lists into two parts, and then sort each part and merge them together.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        // Find the middle of the linked list.
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Break up the linked list into two parts.
        ListNode first = head;
        ListNode second = slow.next;
        slow.next = null;
        
        // Sort each part separately.
        first = sortList(first);
        second = sortList(second);
        
        // Merge the two linked lists.
        ListNode curr = null;
        while (first != null || second != null) {
            ListNode node;
            if (first == null) {
                node = second;
                second = second.next;
            } else if (second == null) {
                node = first;
                first = first.next;
            } else if (first.val < second.val) {
                node = first;
                first = first.next;
            } else {
                node = second;
                second = second.next;
            }
            if (curr == null) {
                head = curr = node;
            } else {
                curr.next = node;
                curr = node;
            }
        }
        
        return head;
    }
}

Insertion Sort List | Leetcode

Sort a linked list using insertion sort.

---

Solution: For each node in the given linked list, insert it in order into a new linked list. Not easy to get the logic right the first time one writes the code.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;

        // Start off a new list reusing the same nodes.        
        ListNode newHead = head;
        head = head.next;
        newHead.next = null;
        
        // Insert each node in order.
        while (head != null) {
            // head.next will be overwritten, so save it first.
            ListNode next = head.next;
            newHead = insertInOrder(newHead, head);
            head = next;
        }
        
        return newHead;
    }
    
    private ListNode insertInOrder(ListNode head, ListNode curr) {
        // Find position at which we should insert curr.
        ListNode prev = null;
        ListNode node = head;
        while (node != null && curr.val > node.val) {
            prev = node;
            node = node.next;
        }
        
        // We might need to insert as the head of the list.
        if (prev == null) {
            curr.next = head;
            return curr;
        }
        
        // Insert as per normal inside the list.
        curr.next = prev.next;
        prev.next = curr;
        return head;
    }
}

LRU Cache | Leetcode

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

---

Solution: The key here is to choose a data structure, or a group of data structures, that will support an efficient implementation of the LRU cache.

For a cache get and set, we need to support an O(1) time lookup and removal of a given key, which basically means that we would need a hashmap. We also need a way to quickly remove the key from an ordered list and then move it to the front of the ordered list. For this, we can use a doubly-linked list for quick insertions and removals when given any node. The insertion and removal should also require only O(1) time, which means that we need to use the hashmap to point to the doubly-linked list node, and not just to the integer value.

For the doubly-linked list, we need to maintain both the head pointer and tail pointer, so that we can quickly insert at the front and also remove the tail node without needing to go through the entire list.

We also need to maintain the number of elements in the LRU cache so that we can remove the oldest node when we reach the maximum capacity. We use the Java hashmap to maintain the size so that we do not have to roll our own variable.

Most of the code turns out to be manipulation operations around the doubly-linked list. The other parts are relatively straightforward.

public class LRUCache {
    
    private static class ListNode {
        int key;
        int value;
        ListNode prev;
        ListNode next;
        ListNode(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private ListNode head;
    private ListNode tail;
    private Map<Integer, ListNode> map = new HashMap<>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        ListNode node = map.get(key);
        if (node == null) return -1;
        
        // Move this node to the head of the list.
        if (node != head) {
            // (head != tail) must be true at this point.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
        }
        
        return node.value;
    }
    
    public void set(int key, int value) {
        // Check existing node for key.
        ListNode node = map.get(key);
        
        if (node != null) {
            // Reuse this node.
            node.value = value;
                
            // Short-circuit when key is already the head node.
            if (node == head) return;
            
            // Remove the old node for key.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
        } else if (map.size() == capacity) {
            // Remove the last node if we have reached capacity.
            map.remove(tail.key);
            
            // Reuse the tail node.
            node = tail;
            node.key = key;
            node.value = value;
            map.put(key, node);

            // Short-circuit if this is the only node in the list.
            if (head == tail) return;
            
            // Remove tail node.
            tail = tail.prev;
            tail.next = null;
        } else {
            // Create a new node as there is none we could reuse.
            node = new ListNode(key, value);
            map.put(key, node);
        }

        // Place the node at the head.
        node.prev = null;
        node.next = head;
        if (head != null) {
            head.prev = node;
        } else {
            tail = node;
        }
        head = node;
    }
}

Binary Tree Postorder Traversal | Leetcode

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

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

   1
    \
     2
    /
   3

return [3,2,1].

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

---

Solution: Use a stack to hold the nodes. For each node we pop, check if this is a leaf node. If so, add its value to the answer list. If not, push a new fake leaf node with the popped node's value, push the right node, and then push the left node. This will simulate the postorder traversal.

/**
 * 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> postorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        
        do {
            TreeNode node = stack.pop();
            if (node.left == null && node.right == null) {
                answer.add(node.val);
                continue;
            }
            stack.push(new TreeNode(node.val));
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } while (!stack.isEmpty());
        
        return answer;
    }
}

Binary Tree Preorder Traversal | Leetcode

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

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

   1
    \
     2
    /
   3

return [1,2,3].

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

---

Solution: Use a stack to hold the nodes. After popping each node, first add the value to the answer, then push the right node, then push the left node.

/**
 * 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> preorderTraversal(TreeNode root) {
        if (root == null) return Collections.emptyList();

        List<Integer> answer = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        do {
            TreeNode node = stack.pop();
            answer.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } while (!stack.isEmpty());

        return answer;
    }
}

Reorder List | Leetcode

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

---

Solution:
1. Break list into two halves (use fast & slow pointers to find the middle node).
2. Reverse the second half.
3. Merge the two halves back together.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // Find the middle of the list.
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        
        // Terminate the first half of the list.
        slow.next = null;
        
        // Reverse the second half of the list.
        ListNode prev = null;
        ListNode curr = mid;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // Merge the two halves together.
        ListNode first = head;
        ListNode second = prev;
        
        while (first != null && second != null) {
            if (first != null) {
                ListNode temp = first.next;
                first.next = second;
                first = temp;
            }
            if (second != null) {
                ListNode temp = second.next;
                second.next = first;
                second = temp;
            }
        }
    }
}

Linked List Cycle II | Leetcode

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

---

Solution: Maintain two pointers slow and fast, where slow advances by one node at a time, and fast advances by two nodes at a time. When they meet, reset slow to the head of the list. Then advance both slow and fast by one node at a time until they meet at the beginning of the cycle.

/**
 * 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 slow = head;
        ListNode fast = head;
        do {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != slow);
        
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

Linked List Cycle | Leetcode

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

---

Solution: Maintain two pointers, slow and fast. Advance slow by one node at a time. Advance fast by two nodes at a time. If slow and fast ever points to the same node, then there is a cycle. If we reach the end of the linked list, then there is no cycle.

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

Word Break II | Leetcode

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

---

Solution: Maintain a list of dictionary words for each position in the string (breakWords[0 .. s.length()]). Iterate the string from first to last position. For each position i, find the list of dictionary words that could be formed and then add it to breakWords[i + word.length()]. This algorithm is similar to the Word Break algorithm, except that in Word Break, we use an array of booleans instead of an array of list of strings.

After we find the array of list of words, gather all the results by maintaining a current list of words going from end to start in the string s and then add each result as we traverse to the beginning of the string.

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String>[] breakWords = new List[s.length() + 1];
        breakWords[s.length()] = new ArrayList<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && breakWords[i] == null) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (!word.equals(s.substring(i, endIndex))) continue;
                
                if (breakWords[endIndex] == null) {
                    breakWords[endIndex] = new ArrayList<>();
                }
                breakWords[endIndex].add(word);
            }
        }
        
        return getResults(new ArrayList<>(), breakWords, s.length(), new ArrayList<>());
    }
    
    private List<String> getResults(List<String> results, List<String>[] breakWords,
            int endIndex, List<String> list) {
        if (endIndex == 0 && list.size() > 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(list.size() - 1));
            for (int i = list.size() - 2; i >= 0; i--) {
                sb.append(' ').append(list.get(i));
            }
            results.add(sb.toString());
        } else if (breakWords[endIndex] != null) {
            for (String word: breakWords[endIndex]) {
                list.add(word);
                getResults(results, breakWords, endIndex - word.length(), list);
                list.remove(list.size() - 1);
            }
        }
        return results;
    }
}

Word Break | Leetcode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

---

Solution: Maintain an array of booleans (canBreak) to mark whether the particular position can be broken up into dictionary words. For example, "canBreak[i] = true" means that the string from characters 0 to (i - 1) can break into dictionary words.

Iterate through the string from first to last position. For each position i, go through all the dictionary words to check whether the word can contribute to the break. Let word be the dictionary word, and endIndex = i + word.length(). Check if "canBreak[i] = true" and "word.equals(s.substring(i, endIndex)) == true". If both conditions were true, then set canBreak[endIndex] = true. If endIndex == s.length(), then we know the whole word can be broken into dictionary words, so return true.

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] canBreak = new boolean[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && !canBreak[i]) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (endIndex < s.length() && canBreak[endIndex]) continue;
                
                if (s.substring(i, endIndex).equals(word)) {
                    if (endIndex == s.length()) return true;
                    canBreak[endIndex] = true;
                }
            }
        }
        
        return false;
    }
}

Copy List with Random Pointer | Leetcode

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

---

Solution: Iterate through the list from beginning to end, creating a clone node for each node in the list. Put all these clone nodes in a hashmap.

Iterate through the list again, this time linking up the next and random pointers of all the clone nodes.

Return the clone node of the head node as the answer.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        Map<Integer, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        do {
            map.put(cur.label, new RandomListNode(cur.label));
            cur = cur.next;
        } while (cur != null);
        
        cur = head;
        do {
            RandomListNode node = map.get(cur.label);
            if (cur.next != null) {
                node.next = map.get(cur.next.label);
            }
            if (cur.random != null) {
                node.random = map.get(cur.random.label);
            }
            cur = cur.next;
        } while (cur != null);
        
        return map.get(head.label);
    }
}

Single Number II | Leetcode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

---

Solution: Count the number of one bits in the i-th bit position among all the numbers in the array (where i=0..31). If the count is not a multiple of 3, then set the i-th bit of the answer number as 1. When we have iterated from i=0 to i=31, then we would have obtained the complete answer number, so just return it.

Algorithm 1: Easy to Understand

public class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (1 << i);
            int bitCount = 0;
            for (int n: nums) {
                if ((n & bit) != 0) bitCount++;
            }
            if ((bitCount % 3) != 0) answer |= bit;
        }
        return answer;
    }
}

Algorithm 2: Probably No Need to Memorize (https://leetcode.com/discuss/43377/the-simplest-solution-ever-with-clear-explanation)

public class Solution {
    public int singleNumber(int[] nums) {
        int n0 = 0;
        int n1 = 0;
        for (int n: nums) {
            n0 = (n0 ^ n) & (~n1);
            n1 = (n1 ^ n) & (~n0);
        }
        return n0;
    }
}

Single Number | Leetcode

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

---

Solution: This is a trick question. Use XOR through all the numbers to get the answer.

public class Solution {
    public int singleNumber(int[] nums) {
        int n = nums[0];
        for (int i = 1; i < nums.length; i++) {
            n ^= nums[i];
        }
        return n;
    }
}

Candy | Leetcode

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

---

Solution: Create an array of all ones, indicating the number of candies we will give to each child.

Go from left to right. If the right neighbor (at index i) has a higher rating than the left neighbor (at index i - 1), then give the right neighbor one more candy than the left neighbor.

Go from right to left. If the left neighbor (at index i - 1) has a higher rating than the right neighbor (at index i), then give the left neighbor one more candy than the right neighbor. But also make sure that the left neighbor has at least as many candies as what we previously decided to give to this child so that we continue to satisfy the condition for going from left to right as well.

Sum up the number of candies for each child as the answer.

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i - 1] < ratings[i]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        for (int i = ratings.length - 1; i >= 1; i--) {
            if (ratings[i - 1] > ratings[i]) {
                candies[i - 1] = Math.max(candies[i - 1], candies[i] + 1);
            }
        }
        
        return IntStream.of(candies).sum();
    }
}

Gas Station | Leetcode

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

---

Solution: For each starting point i, check from index i to index n - 1 (where n is the circuit length), and then from 0 to i - 1. At each gas station, fill up the tank and travel to the next gas station, which is tank += gas[i] - cost[i]. If at any point the tank falls to negative (0 is ok), then this starting point i will not work. If we manage to get through the entire circuit with tank >= 0, then i is the answer.

The key step is to avoid an O(N^2) time algorithm and use an O(N) time algorithm. For example, at starting point i=4, we check indexes 4, 5, 6 and 7, and at index=7, the tank falls to negative. There is no need to check for starting points i=5, 6, and 7 again. Thus we can skip from i=4 directly to i=8. Doing this will make sure that we iterate through the circuit only once to get the answer, thus an O(N) algorithm.

If we use an O(N^2) algorithm, it will not pass the Leetcode submission.

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int tank = 0;
            for (int j = 0, index = i; j < gas.length; j++, index++) {
                if (index == gas.length) index = 0;
                tank += gas[index] - cost[index];
                if (tank < 0) {
                    // Key step: begin next loop from j.
                    if (j > i) i = j;
                    break;
                }
            }
            if (tank >= 0) return i;
        }
        return -1;
    }
}

Clone Graph | Leetcode

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
 
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

---

Solution: A tricky breadth-first search (BFS) algorithm. The main trick is to add the node to the seen set as soon as you put it in the BFS queue. If you put it in the seen set after you pop the node from the queue, then you run a risk of having duplicates, which means you will not pass the Leetcode submission.

For each loop of the BFS, add all the neighbors to the BFS queue, but do not recurse into their neighbors yet.

Maintain a hashmap of all new nodes created so far so that we do not create the same node twice.

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        
        Set<Integer> seen = new HashSet<>();
        Map<Integer, UndirectedGraphNode> newNodes = new HashMap<>();
        LinkedList<UndirectedGraphNode> bfsQueue = new LinkedList<>();
        bfsQueue.addLast(node);
        seen.add(node.label);
        
        do {
            UndirectedGraphNode curNode = bfsQueue.removeFirst();
            UndirectedGraphNode newNode = getOrCreateCloneNode(newNodes, curNode.label);
            for (UndirectedGraphNode neighbor: curNode.neighbors) {
                newNode.neighbors.add(getOrCreateCloneNode(newNodes, neighbor.label));
                if (!seen.contains(neighbor.label)) {
                    bfsQueue.addLast(neighbor);
                    seen.add(neighbor.label);
                }
            }
        } while (!bfsQueue.isEmpty());
        
        return newNodes.get(node.label);
    }
    
    private UndirectedGraphNode getOrCreateCloneNode(
            Map<Integer, UndirectedGraphNode> newNodes, int label) {
        UndirectedGraphNode newNode = newNodes.get(label);
        if (newNode == null) {
            newNode = new UndirectedGraphNode(label);
            newNodes.put(label, newNode);
        }
        return newNode;
    }
}

Palindrome Partitioning II | Leetcode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

---

Solution: This is a 1D dynamic programming problem. One additional trick is to cache the substring palindrome check in a 2D matrix so that we do not have to recompute that multiple times over.

The DP formula is:

f(i) = 0 : if substring from 0 to i is a palindrome
       min(f[j] + 1) : where j = 0 to i - 1, if substring from j + 1 to i is a palindrome

The answer is then taken from f(len(s) - 1).

Reference: http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html

public class Solution {
    public int minCut(String s) {
        // Cache palindrome evaluation matrix.
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                isPalindrome[i][j] = (s.charAt(i) == s.charAt(j))
                        && (((j - i) <= 1) || isPalindrome[i + 1][j - 1]);
            }
        }
        
        // Dynamic programming loop.
        int[] numCuts = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome[0][i]) {
                numCuts[i] = 0;
                continue;
            }
            numCuts[i] = s.length();
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    numCuts[i] = Math.min(numCuts[i], numCuts[j] + 1);
                }
            }
        }
        
        return numCuts[s.length() - 1];
    }
}

Palindrome Partitioning | Leetcode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

---

Solution: Recursively process the string, cutting off an initial portion of it and recursing on the rest of the string. When we reach an empty string, add the result only if the current list of strings is not empty.

The algorithm is very similar to that of getting all possible combinations of substrings within the string except that the characters within all substrings must appear in the same sequence as the characters in the original string. We add one more check, isPalindrome(), to each substring, to see if any particular combination should be accepted or not.

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> answer = new ArrayList<>();
        process(answer, new ArrayList<String>(), s);
        return answer;
    }
    
    private void process(List<List<String>> answer, List<String> list, String s) {
        if (s.length() == 0) {
            if (!list.isEmpty()) {
                answer.add(new ArrayList<String>(list));
            }
            return;
        }
        for (int i = 1; i <= s.length(); i++) {
            String t = s.substring(0, i);
            if (!isPalindrome(t)) continue;
            list.add(t);
            process(answer, list, s.substring(i));
            list.remove(list.size() - 1);
        }
    }
    
    private boolean isPalindrome(String s) {
        if (s.length() == 1) return true;
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}

Surrounded Regions | Leetcode

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

---

Solution: Iterate through all non-edge cells in the board in any order. For each O, perform BFS to obtain all reachable O's. If the BFS did not find a way to the edge of the board, then mark all BFS-reachable cells as X.

public class Solution {

    private final Set<Integer> seenOs = new HashSet<>();
    private final Set<Integer> bfsSeenOs = new HashSet<>();
    private final LinkedList<Integer> bfsQueue = new LinkedList<>();
    private int height;
    private int width;
    private boolean foundWayOut;
        
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        
        height = board.length;
        width = board[0].length;
        
        // No need to go through the cells at the board edges since we will never
        // convert them to X's.
        for (int y = height - 2; y >= 1; y--) {
            for (int x = width - 2; x >= 1; x--) {
             // If this is an X, ignore it since we cannot do anything with it.
                if (board[y][x] == 'X') continue;
                
                // Calculate the number this cell represents.
                int n = (y * width) + x;
                
                // If we have already visited this O, then skip it.
                if (seenOs.contains(n)) continue;

                // Perform BFS starting from current cell.
                bfsSeenOs.add(n);                
                bfsQueue.add(n);
                foundWayOut = false;
                
                do {
                    int bfsN = bfsQueue.removeFirst();
                    int bfsY = bfsN / width;
                    int bfsX = bfsN % width;

                    // Check each neighbor to see if we should add it to the BFS queue.
                    if (bfsY > 0)          bfsCheckAddNeighbor(board, bfsY - 1, bfsX);
                    if (bfsY < height - 1) bfsCheckAddNeighbor(board, bfsY + 1, bfsX);
                    if (bfsX > 0)          bfsCheckAddNeighbor(board, bfsY, bfsX - 1);
                    if (bfsX < width - 1)  bfsCheckAddNeighbor(board, bfsY, bfsX + 1);
                    
                } while (!bfsQueue.isEmpty());

                // Mark all current BFS-reachable nodes as seen.
                seenOs.addAll(bfsSeenOs);
                
                // If we did not find a way out, then change all reachable O's to X's.
                if (!foundWayOut) {
                    for (int m: bfsSeenOs) {
                        board[m / width][m % width] = 'X';
                    }
                }

                bfsSeenOs.clear();
            }
        }
    }
    
    private void bfsCheckAddNeighbor(char[][] board, int y, int x) {
     // Skip all X's.
        if (board[y][x] == 'X') return;
        
        int n = (y * width) + x;
        
        // If we have already visited this cell in this BFS, skip it.
        if (bfsSeenOs.contains(n)) return;

        // These two collections are very similar, but are used differently.
        // The set is for quick add/get. The queue is for linear iteration.
        bfsSeenOs.add(n);
        bfsQueue.add(n);
        
        // If this cell is at the edge of the board, then we have found a way out!
        if (y == 0 || y == height - 1 || x == 0 || x == width - 1) {
            foundWayOut = true;
        }
    }

}

Sum Root to Leaf Numbers | Leetcode

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

---

Solution: Recurse down the tree, but don't recurse onto null nodes. For each recursion, multiply the previous value by 10 and add the current node's value. When you reach a leaf node, return the value. If you hit a non-leaf node, take the sum of the left and right children, but count null children nodes as zero.

/**
 * 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 sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return sum(root, 0);
    }
    
    private int sum(TreeNode node, int n) {
        int i = (n * 10) + node.val;
        if (node.left == null && node.right == null) return i;
        
        int s = 0;
        if (node.left != null) s += sum(node.left, i);
        if (node.right != null) s += sum(node.right, i);
        return s;
    }
}

Longest Consecutive Sequence | Leetcode

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

---

Solution: Put all the numbers into a hashset. Then for each number, go in increasing order and in decreasing order to find all adjacent numbers. Keep track of the maximum adjacent length found so far. Remove each number as you encounter it as you will never need it again.

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;

        Set<Integer> set = new HashSet<>();
        for (int i: nums) set.add(i);
        
        int longest = 1;
        
        do {
            // A not-so-elegant way to extract a random element from the set.
            int n = set.iterator().next();
            set.remove(n);

            int length = 1;
            
            for (int i = n + 1; set.contains(i); i++) {
                length++;
                set.remove(i);
            }

            for (int i = n - 1; set.contains(i); i--) {
                length++;
                set.remove(i);
            }
            
            if (length > longest) longest = length;
        } while (!set.isEmpty());
        
        return longest;
    }
}

Word Ladder | Leetcode

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

Solution: Perform a Breadth-First Search (BFS) by using a queue to hold the nodes. For each word, for each character, iterate from 'a' to 'z' to form all possible next words from the current word. For each next possible word, if it were found in the dictionary, then append it to the queue, with a cost of one more than the current cost.

The key is to remove words from the dictionary as you encounter them. This will ensure that you will not get into an infinite loop.

public class Solution {
    private static class WordNode {
        private String word;
        private int cost;
        
        private WordNode(String word, int cost) {
            this.word = word;
            this.cost = cost;
        }
    }
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord.equals(endWord)) return 1;

        LinkedList<WordNode> queue = new LinkedList<>();
        queue.add(new WordNode(beginWord, 1));

        do {
            WordNode wordNode = queue.removeFirst();
            char[] a = wordNode.word.toCharArray();

            for (int i = 0; i < a.length; i++) {
                char savedChar = a[i];

                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (newWord.equals(endWord)) return wordNode.cost + 1;
                    if (wordDict.contains(newWord)) {
                        queue.addLast(new WordNode(newWord, wordNode.cost + 1));
                        wordDict.remove(newWord);
                    }
                }

                a[i] = savedChar;
            }
        } while (!queue.isEmpty());

        return 0;
    }
}

Word Ladder II | Leetcode

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

---

Solution: https://leetcode.com/discuss/9523/share-two-similar-java-solution-that-accpted-by-oj

Algorithm 1: Slow (Will Not Pass Leetcode)

public class Solution {
    private static class WordNode {
        private final String word;
        private final int cost;
        private final WordNode prev;
        
        private WordNode(String word, int cost, WordNode prev) {
            this.word = word;
            this.cost = cost;
            this.prev = prev;
        }
    }
    
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> answer = new ArrayList<>();
        LinkedList<WordNode> queue = new LinkedList<>();
        queue.addLast(new WordNode(start, 1, null));
        dict.remove(start);
        int minCost = 0;
        
        do {
            WordNode node = queue.removeFirst();
            if (minCost != 0 && node.cost > minCost) break;
            
            char[] a = node.word.toCharArray();
            for (int i = 0; i < a.length; i++) {
                char ch = a[i];

                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == ch) continue;
                    a[i] = c;
                    String s = new String(a);
                    if (s.equals(end)) {
                        if (minCost == 0 || node.cost == minCost) {
                            answer.add(formResult(node, end));
                            minCost = node.cost;
                            continue;
                        }
                    }
                    if (!dict.contains(s)) continue;
                    queue.addLast(new WordNode(s, node.cost + 1, node));
                }
                
                a[i] = ch;
            }
        } while (!queue.isEmpty());
        
        return answer;
    }
    
    private static List<String> formResult(WordNode node, String end) {
        LinkedList<String> list = new LinkedList<>();
        list.addFirst(end);
        while (node != null) {
            list.addFirst(node.word);
            node = node.prev;
        }
        return list;
    }
}

Algorithm 2: Fast (Will Pass Leetcode)

public class Solution {
    private List<List<String>> answer = new ArrayList<List<String>>();
    private LinkedList<String> backTraceList = new LinkedList<String>();
    private Map<String, List<String>> adjacentWordsMap = new HashMap<String, List<String>>();

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        int curr = 1;
        int next = 0;
        boolean found = false;

        LinkedList<String> queue = new LinkedList<>();
        Set<String> unvisited = new HashSet<String>(dict);
        Set<String> visited = new HashSet<String>();

        queue.add(start);
        unvisited.add(end);
        unvisited.remove(start);

        do {
            String word = queue.removeFirst();
            curr--;
            char[] a = word.toCharArray();
            for (int i = 0; i < word.length(); i++) {
                char savedChar = a[i];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (unvisited.contains(newWord)) {
                        // Key statement - avoid duplicate queue insertion.
                        if (!visited.contains(newWord)) {
                            visited.add(newWord);
                            next++;
                            queue.addLast(newWord);
                        }

                        // Build adjacency graph.
                        List<String> list = adjacentWordsMap.get(newWord);
                        if (list == null) {
                            list = new LinkedList<String>();
                            adjacentWordsMap.put(newWord, list);
                        }
                        list.add(word);

                        if (newWord.equals(end)) found = true;
                    }
                }
                a[i] = savedChar;
            }
            
            if (curr == 0) {
                if (found) break;
                curr = next;
                next = 0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        } while (!queue.isEmpty());

        backTrace(end, start);

        return answer;
    }

    private void backTrace(String word, String start) {
        if (word.equals(start)) {
            backTraceList.addFirst(start);
            answer.add(new ArrayList<String>(backTraceList));
            backTraceList.removeFirst();
            return;
        }
        backTraceList.addFirst(word);
        if (adjacentWordsMap.containsKey(word)) {
            for (String s : adjacentWordsMap.get(word)) {
                backTrace(s, start);
            }
        }
        backTraceList.removeFirst();
    }
}

Valid Palindrome | Leetcode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
 
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

---

Solution: Maintain two pointers, one pointing to the beginning of the string, and the other pointing to the end of the string. Advance first pointer to a position where it is an alpha-numeric character. Retreat last pointer to a position where it is an alpha-numeric character. If the character at the first pointer is not the same as the character at the last pointer, then return false. Repeat until done (first >= last). Return true if you did not discover any inequalities.

public class Solution {
    public boolean isPalindrome(String s) {
        int first = 0;
        int last = s.length() - 1;
        int ch1, ch2;
        
        while (first < last) {
            while (true) {
                ch1 = s.charAt(first++);
                if (Character.isLetterOrDigit(ch1)) break;
                if (first >= last) return true;
            }
            
            while (true) {
                ch2 = s.charAt(last--);
                if (Character.isLetterOrDigit(ch2)) break;
                if (first >= last) return true;
            }
            
            if (Character.toUpperCase(ch1) != Character.toUpperCase(ch2)) {
                return false;
            }
        }
        
        return true;
    }
}

Binary Tree Maximum Path Sum | Leetcode

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

---

Solution: Recurse through the tree, keeping track of the maximum path sum ever found. For each node, we can compute the max by considering branching out to both left and right sub-trees. But to return the max sum for the current node, we can only take one path, either the node itself only, or the node + the left sub-tree, or the node + the right sub-tree. Return the maximum path sum ever found as the answer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum;
    
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        maxSum = root.val;
        recurse(root);
        return maxSum;
    }
    
    private int recurse(TreeNode node) {
        if (node == null) return 0;
        
        int left = recurse(node.left);
        int right = recurse(node.right);
        
        // For the current node, pick only a single path.
        int current = Math.max(node.val, Math.max(node.val + left, node.val + right));
        
        // For maxSum, we can pick two paths both branching out from node.
        maxSum = Math.max(maxSum, Math.max(current, node.val + left + right));
        
        return current;
    }
}

Best Time to Buy and Sell Stock III | Leetcode

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Solution: Use linear dynamic programming twice on the array. The first time is from left to right. The second time is from right to left. Each time, capture the maximum profit possible until the given point, either from the left end or the right end. At the end, go through the array one last time, and split the array into two parts, getting the maximum profit from the left part plus the right part.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;

        int[] leftProfit = new int[prices.length];
        int[] rightProfit = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            int left = (min < prices[i]) ? (prices[i] - min) : 0;
            leftProfit[i] = Math.max(left, leftProfit[i - 1]);
            min = Math.min(min, prices[i]);
        }
        
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            int right = (max > prices[i]) ? (max - prices[i]) : 0;
            rightProfit[i] = Math.max(right, rightProfit[i + 1]);
            max = Math.max(max, prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = -1; i < prices.length; i++) {
            int left = (i < 0) ? 0 : leftProfit[i];
            int right = (i + 1 < prices.length) ? rightProfit[i + 1] : 0;
            maxProfit = Math.max(maxProfit, left + right);
        }
        
        return maxProfit;
    }
}

Best Time to Buy and Sell Stock II | Leetcode

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Solution: Iterate through the prices array from beginning to end. Find the current lowest price, which is defined as the price which is lower than its next price. Then find the current highest price, which is defined as the price which is higher than its next price. Capture the profit by subtracting the current lowest price from the current highest price. Repeat until we reach the end of the loop.

The boundary cases are very tricky, so have to be extra careful.

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        int last = prices.length - 1;
        int i = 0;
        do {
            // Find the current lowest point.
            while (i < last && prices[i] >= prices[i + 1]) i++;
            if (i >= last) break;
            int lo = prices[i++];
            
            // Find the current highest point.
            while (i <= last && prices[i - 1] <= prices[i]) i++;
            int hi = prices[i - 1];
            
            // Capture current profit if any.
            if (hi > lo) profit += hi - lo;
        } while (i < last);
        return profit;
    }
}

Best Time to Buy and Sell Stock | Leetcode

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

---

Solution: Go through each price, at the same time keeping the minimum price and maximum profit ever seen so far. By using the current price and this minimum price, we can calculate the maximum profit attainable.

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

Triangle | Leetcode

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

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

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

---

Solution: Allocate two arrays to hold the intermediate results. Initialize an array by copying the values from the last row of the triangle. Loop from the second last row of the triangle to the top. In each iteration, compute the minimum path sum of the next top row, and then swap the two arrays for next reuse. When done, the answer is stored as the first element of the current array.

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0) return 0;
        if (triangle.size() == 1) return triangle.get(0).get(0);

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

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

Pascal's Triangle II | Leetcode

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

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

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

---

Solution: Edit the same array in-place. For index i, since we are going to use indexes i-1 and i to update index i, we need to save the pre-modified value at index i to calculate the next value.

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

Pascal's Triangle | Leetcode

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

For example, given numRows = 5,

Return

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

---

Solution: Start off with the base case, with the first list having only one element "1". For each additional list, put a "1" at the beginning and another "1" at the end. For each element in the middle, add the two adjacent elements from the list at the top to get the element's value.

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();
        if (numRows == 0) return answer;
        answer.add(Arrays.asList(1));
        for (int i = 1; i < numRows; i++) {
            List<Integer> lastList = answer.get(i - 1);
            List<Integer> curList = new ArrayList<>();
            answer.add(curList);
            curList.add(1);
            for (int j = 0; j < lastList.size() - 1; j++) {
                curList.add(lastList.get(j) + lastList.get(j + 1));
            }
            curList.add(1);
        }
        return answer;
    }
}

Populating Next Right Pointers in Each Node II | Leetcode

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

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

Note:

• You may only use constant extra space.

For example,

Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

---

Solution: The trick is to use the linked list of a level to fill up the next lower level. Maintain the first node (curFirst) of the linked list. At the beginning of each loop, set the current node (curNode) to the first node. Then for each left and right children, link them up as you traverse the level from left to right. For the first non-null child node you find, set it to be the first node.

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode curFirst = root;
        TreeLinkNode curNode;
        TreeLinkNode nextNode;
        
        while (curFirst != null) {
            curNode = curFirst;
            curFirst = null;
            nextNode = null;
            
            do {
                if (curNode.left != null) {
                    if (nextNode == null) {
                        nextNode = curNode.left;
                        if (curFirst == null) curFirst = nextNode;
                    } else {
                        nextNode = nextNode.next = curNode.left;
                    }
                }
                
                if (curNode.right != null) {
                    if (nextNode == null) {
                        nextNode = curNode.right;
                        if (curFirst == null) curFirst = nextNode;
                    } else {
                        nextNode = nextNode.next = curNode.right;
                    }
                }
                
                curNode = curNode.next;
            } while (curNode != null);
        }
    }
}

Populating Next Right Pointers in Each Node | Leetcode

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

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

---

Solution: Terminate the linked list of the root node first. Maintain two queues, first queue (curLevel) is the current level of the tree, second queue (nextLevel) is the next level of the tree. For each level, maintain a previous node (prevNode). Link the previous node to the current node. When you are done iterating through the entire tree, the linking is done.

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        root.next = null;
        
        // Iterate through each level of the tree.
        Queue<TreeLinkNode> curLevel = new LinkedList<>();
        Queue<TreeLinkNode> nextLevel = new LinkedList<>();
        
        if (root.left != null) curLevel.add(root.left);
        if (root.right != null) curLevel.add(root.right);
        
        while (!curLevel.isEmpty()) {
            TreeLinkNode prevNode = null;
            do {
                TreeLinkNode curNode = curLevel.remove();
                if (curNode.left != null) nextLevel.add(curNode.left);
                if (curNode.right != null) nextLevel.add(curNode.right);
                if (prevNode != null) prevNode.next = curNode;
                prevNode = curNode;
            } while (!curLevel.isEmpty());
            
            // Terminate the current level linked list.
            if (prevNode != null) prevNode.next = null;
            
            // Swap the curLevel and nextLevel queues.
            Queue<TreeLinkNode> temp = curLevel;
            curLevel = nextLevel;
            nextLevel = temp;
        }
    }
}

Distinct Subsequences | Leetcode

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

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

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

---

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

Good detailed explanation can be found in stackoverflow: http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation

public class Solution {
    public int numDistinct(String s, String t) {
        int[] f = new int[t.length() + 1];
        f[t.length()] = 1;

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

Flatten Binary Tree to Linked List | Leetcode

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

 

Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

---

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

We are basically not using the hint of pre-order traversal in any way.

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