Tuesday, July 21, 2015

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

Monday, July 20, 2015

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;
    }
}

Saturday, July 18, 2015

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;
        }
    }

}

Friday, July 17, 2015

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;
    }
}