Buttercola: September 2015

Wednesday, September 30, 2015

Leetcode: Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Understand the problem:
It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution.

A DFS Solution:

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
         
        int m = rooms.length;
        int n = rooms[0].length;
         
        boolean[][] visited = new boolean[m][n];
         
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, visited, rooms);
                }
            }
        }
    }
     
    private void wallsAndGatesHelper(int row, int col, int distance, boolean[][] visited, int[][] rooms) {
        int rows = rooms.length;
        int cols = rooms[0].length;
         
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
         
        // visited
        if (visited[row][col]) {
            return;
        }
         
        // Is wall?
        if (rooms[row][col] == -1) {
            return;
        }
         
        // Distance greater than current
        if (distance > rooms[row][col]) {
            return;
        }
         
         
        // Mark as visited
        visited[row][col] = true;
         
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
         
        // go up, down, left and right
        wallsAndGatesHelper(row - 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row + 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col - 1, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col + 1, distance + 1, visited, rooms);
         
        // Mark as unvisited
        visited[row][col] = false;
    }
}

A BFS Solution:

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
         
        int m = rooms.length;
        int n = rooms[0].length;
         
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, rooms, queue);
                }
            }
        }
    }
     
    private void wallsAndGatesHelper(int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        fill(row, col, distance, rooms, queue);
         
        int m = rooms.length;
        int n = rooms[0].length;
         
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cord = queue.poll();
                int x = cord / n;
                int y = cord % n;
             
                fill(x - 1, y, distance + 1, rooms, queue);
                fill(x + 1, y, distance + 1, rooms, queue);
                fill(x, y - 1, distance + 1, rooms, queue);
                fill(x, y + 1, distance + 1, rooms, queue);
             
            }
            distance++;
        }
    }
     
    private void fill (int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        int m = rooms.length;
        int n = rooms[0].length;
         
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return;
        }
         
        if (rooms[row][col] == -1) {
            return;
        }
         
        if (distance > rooms[row][col]) {
            return;
        }
         
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
         
        int cord = row * n + col;
        queue.offer(cord);
    }
}

Leetcode: Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
Since the problem requires to maintain the relative order of the array, we cannot simply swap the numbers in the array.

One simple way is very similar to remove the duplicated numbers in the array. In the first pass, we move all the non-zero elements upfront and fill out all the zero slots. Then we just need to append 0s at the end of the array.

Code (Java):

public class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
         
        int i = 0;
        int j = 0;
         
        // Step 1: compress the nums array by filling out the 0s
        while (i < nums.length) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
                i++;
            } else {
                i++;
            }
        }
         
        // Append 0s to the end
        while (j < nums.length) {
            nums[j] = 0;
            j++;
        }
    }
}

Tuesday, September 29, 2015

Leetcode: Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

Think of "looking ahead". You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google's guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Code (Java):

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> iterator;
    private int peekedElement;
    private boolean hasPeekedElement;
 
 public PeekingIterator(Iterator<Integer> iterator) {
     // initialize any member here.
     this.iterator = iterator;
     if (iterator.hasNext()) {
         hasPeekedElement = true;
         peekedElement = iterator.next();
     }
 }
 
    // Returns the next element in the iteration without advancing the iterator.
 public Integer peek() {
        return peekedElement;
 }
 
 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 @Override
 public Integer next() {
     int ret = peekedElement;
     if (iterator.hasNext()) {
         peekedElement = iterator.next();
     } else {
         hasPeekedElement = false;
     }
     return ret;
 }
 
 @Override
 public boolean hasNext() {
     return iterator.hasNext() || hasPeekedElement;
 }
}

Update on 10/14/15:

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> it;
    private int peakElement;
    private boolean peaked;
 public PeekingIterator(Iterator<Integer> iterator) {
     // initialize any member here.
     this.it = iterator;
     peakElement = 0;
     peaked = false;
 }
 
    // Returns the next element in the iteration without advancing the iterator.
 public Integer peek() {
        if (!peaked) {
            peakElement = it.next();
            peaked = true;
        }
        return peakElement;
 }
 
 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 @Override
 public Integer next() {
     int ans = 0;
     if (peaked) {
         ans = peakElement;
         peaked = false;
     } else {
         ans = it.next();
     }
      
     return ans;
 }
 
 @Override
 public boolean hasNext() {
     return peaked == true || it.hasNext();
 }
}

Wednesday, September 16, 2015

Leetcode: Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

The knight's health has no upper bound.
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

Understand the problem:
A matrix DP problem. We could start from the bottom-right corner, i.e, dungeon[m - 1][n - 1].

-- Define dp[i][j] means the min HP value from i, j to the bottom-right corner.
-- Initialization: dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
-- Transit function: dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
-- Final state dp[0][0].

Code (Java):

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null) {
            return 0;
        }
         
        int m = dungeon.length;
        int n = dungeon[0].length;
         
        int[][] dp = new int[m][n];
         
        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
         
        // Initialization the last column
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
         
        // Initialization the last row
        for (int i = n - 2; i >= 0; i--) {
            dp[m - 1][i] = Math.max(1, dp[m - 1][i + 1] - dungeon[m - 1][i]);
        }
         
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], 
                   dp[i][j + 1]) - dungeon[i][j]);
            }
        }
         
        return dp[0][0];
    }
}

Tuesday, September 15, 2015

Leetcode: Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

Understand the problem:
The idea would be very close to the previous problem. So we find all the strobogrammatic numbers between the length of low and high. Note that when the n == low or n == high, we need to compare and make sure the strobogrammatic number we find is within the range.

Code (Java):

public class Solution {
    private int count = 0;
    private Map<Character, Character> map = new HashMap<>();
     
    public int strobogrammaticInRange(String low, String high) {
        if (low == null || low.length() == 0 || high == null || high.length() == 0) {
            return 0;
        }
         
        fillMap();
         
        for (int n = low.length(); n <= high.length(); n++) {
            char[] arr = new char[n];
            getStrobogrammaticNumbers(arr, 0, n - 1, low, high);
        }
         
        return count;
    }
     
    private void getStrobogrammaticNumbers(char[] arr, int start, int end, String low, String high) {
        if (start > end) {
            String s = new String(arr);
            if ((s.length() == 1 || s.charAt(0) != '0') && compare(low, s) && compare(s, high)) {
                count++;
            }
            return;
        }
             
        for (char c : map.keySet()) {
            arr[start] = c;
            arr[end] = map.get(c);
                 
            if ((start < end) || (start == end && map.get(c) == c)) {
                getStrobogrammaticNumbers(arr, start + 1, end - 1, low, high);
            }
        }
    }
     
    // Return true if s1 <= s2
    private boolean compare(String s1, String s2) {
        if (s1.length() == s2.length()) {
            if (s1.compareTo(s2) <= 0) {
                return true;
            } else {
                return false;
            }
        }
         
        return true;
    }
     
    private void fillMap() {
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');
        map.put('6', '9');
        map.put('9', '6');
    }
}

Leetcode: Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

You may assume all letters are in lowercase.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

Understand the problem:
The problem can be solved by a topological sorting. First we construct the graph based on the ordering relationship. Then do a topological sorting, which return the correct order.

Code (Java):

public class Solution {
    public String alienOrder(String[] words) {
        // Step 1: build the graph
        Map<Character, Set<Character>> graph = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String curr = words[i];
            for (int j = 0; j < curr.length(); j++) {
                if (!graph.containsKey(curr.charAt(j))) {
                    graph.put(curr.charAt(j), new HashSet<Character>());
                }
            }
             
            if (i > 0) {
                connectGraph(graph, words[i - 1], curr);
            }
        }
         
        // Step 2: toplogical sorting
        StringBuffer sb = new StringBuffer();
        Map<Character, Integer> visited = new HashMap<Character, Integer>();
         
        Iterator it = graph.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            char vertexId = (char) pair.getKey();
            if (toplogicalSort(vertexId, graph, sb, visited) == false) {
                return "";
            }
        }
         
        return sb.toString();
    }
     
    private void connectGraph(Map<Character, Set<Character>> graph, String prev, String curr) {
        if (prev == null || curr == null) {
            return;
        }
         
        int len = Math.min(prev.length(), curr.length());
         
        for (int i = 0; i < len; i++) {
            char p = prev.charAt(i);
            char q = curr.charAt(i);
            if (p != q) {
                if (!graph.get(p).contains(q)) {
                    graph.get(p).add(q);
                }
                break;
            }
        }
    }
     
    private boolean toplogicalSort(char vertexId, Map<Character, Set<Character>> graph, StringBuffer sb, 
                                   Map<Character, Integer> visited) {
        if (visited.containsKey(vertexId)) {
            // visited
            if (visited.get(vertexId) == -1) {
                return false;
            }
             
            // already in the list
            if (visited.get(vertexId) == 1) {
                return true;
            }
        } else {
            // mark as visited
            visited.put(vertexId, -1);
        }
         
        Set<Character> neighbors = graph.get(vertexId);
        for (char neighbor : neighbors) {
            if (toplogicalSort(neighbor, graph, sb, visited) == false) {
                return false;
            }
        }
         
        sb.insert(0, vertexId);
        visited.put(vertexId, 1);
         
        return true;
    }
}

Update on 4/22/19: Topological sort using BFS

public class Solution {
    /**
     * @param words: a list of words
     * @return: a string which is correct order
     */
    public String alienOrder(String[] words) {
        // Write your code here
        if (words == null || words.length == 0) {
            return "";
        }
         
        // step 1: construct the graph
        //
        Map<Character, List<Character>> adjList = new HashMap<>();
        constructGraph(words, adjList);
         
        int numNodes = adjList.size();
         
        StringBuilder ans = new StringBuilder();
         
        // toplogical sorting
        //
        Map<Character, Integer> indegreeMap = new HashMap<>();
        for (Character node : adjList.keySet()) {
            indegreeMap.put(node, 0);
        }
         
        for (Character node : adjList.keySet()) {
            for (Character neighbor : adjList.get(node)) {
                int indegree = indegreeMap.get(neighbor);
                indegree += 1;
                indegreeMap.put(neighbor, indegree);
            }
        }
         
        Queue<Character> queue = new PriorityQueue<>();
        for (Character node : indegreeMap.keySet()) {
            if (indegreeMap.get(node) == 0) {
                queue.offer(node);
            }
        }
         
        while (!queue.isEmpty()) {
            char curNode = queue.poll();
            ans.append(curNode);
             
            for (char neighbor : adjList.get(curNode)) {
                int indegree = indegreeMap.get(neighbor);
                indegree -= 1;
                indegreeMap.put(neighbor, indegree);
                if (indegree == 0) {
                    queue.offer(neighbor);
                }
            }
        }
         
        if (ans.length() < numNodes) {
            return "";
        }
         
        return ans.toString();
    }
     
    private void constructGraph(String[] words, Map<Character, List<Character>> adjList) {
        // construct nodes
        //
        for (String word : words) {
            for (Character c : word.toCharArray()) {
                adjList.put(c, new ArrayList<>());
            }
        }
         
        // construct edges
        //
        for (int i = 1; i < words.length; i++) {
            String prev = words[i - 1];
            String curr = words[i];
             
            for (int j = 0; j < prev.length() && j < curr.length(); j++) {
                if (prev.charAt(j) != curr.charAt(j)) {
                    adjList.get(prev.charAt(j)).add(curr.charAt(j));
                    break;
                }
            }
        }
    }
}

Monday, September 14, 2015

Leetcode: Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Understand the problem:
A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5]
So we could actually observe that there is pattern that
A[even] <= A[odd],
A[odd] >= A[even].

Therefore we could go through the array and check this condition does not hold, just swap.

Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
         
        for (int i = 0; i < nums.length - 1; i++) {
            if (i % 2 == 0) {
                if (nums[i] > nums[i + 1]) {
                    swap(nums, i, i + 1);
                }
            } else {
                if (nums[i] < nums[i + 1]) {
                    swap(nums, i, i + 1);
                }
            }
        }
    }
     
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Leetcode: Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
This is a DP problem.

-- Define dp[n + 1], where dp[i] means the least number of perfect square numbers for integer i.
-- Initialization. dp[0] = 0. dp[i] = Integer.MAX_VALUE since we calculate the min number
-- Transit function, dp[i] = min(dp[i], dp[i - j * j]), where j * j <= i
-- Final state: dp[n]

Code (Java):

public class Solution {
    public int numSquares(int n) {
        if (n <= 0) {
            return 0;
        }
         
        int[] dp = new int[n + 1];
         
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
         
        return dp[n];
    }
}

Leetocode: Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Code (Java):

public class ZigzagIterator {
    private List<Integer> v1;
    private List<Integer> v2;
    private int i;
    private int j;
    private int listId;
 
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
        this.i = 0;
        this.j = 0;
        this.listId = 0;
    }
 
    public int next() {
        int result = 0;
        if (i >= v1.size()) {
            result = v2.get(j);
            j++;
        } else if (j >= v2.size()) {
            result = v1.get(i);
            i++;
        } else {
            if (listId == 0) {
                result = v1.get(i);
                i++;
                listId = 1;
            } else {
                result = v2.get(j);
                j++;
                listId = 0;
            }
        }
         
        return result;
    }
 
    public boolean hasNext() {
        return i < v1.size() || j < v2.size();
    }
}

/** * Your ZigzagIterator object will be instantiated and called as such: * ZigzagIterator i = new ZigzagIterator(v1, v2); * while (i.hasNext()) v[f()] = i.next(); */ Update on 5/14/19:

public class ZigzagIterator {
    /*
    * @param v1: A 1d vector
    * @param v2: A 1d vector
    */
    private Iterator<Integer> it1;
    private Iterator<Integer> it2;
    private int count = 0;
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        // do intialization if necessary
        it1 = v1.iterator();
        it2 = v2.iterator();
        count = 0;
    }
 
    /*
     * @return: An integer
     */
    public int next() {
        int ans = 0;
        // write your code here
        if (!it1.hasNext()) {
            ans = (Integer)it2.next();
        } else if (!it2.hasNext()) {
            ans = (Integer)it1.next();
        } else if (count == 0) {
            ans = (Integer) it1.next();
            count = 1;
        } else {
            ans = (Integer) it2.next();
            count = 0;
        }
 
        return ans;
    }
 
    /*
     * @return: True if has next
     */
    public boolean hasNext() {
        // write your code here
        return it1.hasNext() || it2.hasNext();
    }
}
 
/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator solution = new ZigzagIterator(v1, v2);
 * while (solution.hasNext()) result.add(solution.next());
 * Output result
 */

Tuesday, September 8, 2015

Leetcode: Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

Consider implement these two helper functions:
1. getPredecessor(N), which returns the next smaller node to N.
2. getSuccessor(N), which returns the next larger node to N.
Try to assume that each node has a parent pointer, it makes the problem much easier.
Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
You would need two stacks to track the path in finding predecessor and successor node separately.

Brute-force solution:
The straight-forward solution would be to use a heap. We just treat the BST just as a usual array and do a in-order traverse. Then we compare the current element with the minimum element in the heap, the same as top k problem.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private PriorityQueue&lt;Integer&gt; minPQ;
    private int count = 0;
    public List&lt;Integer&gt; closestKValues(TreeNode root, double target, int k) {
        minPQ = new PriorityQueue&lt;Integer&gt;(k);
        List&lt;Integer&gt; result = new ArrayList&lt;Integer&gt;();
         
        inorderTraverse(root, target, k);
         
        // Dump the pq into result list
        for (Integer elem : minPQ) {
            result.add(elem);
        }
         
        return result;
    }
     
    private void inorderTraverse(TreeNode root, double target, int k) {
        if (root == null) {
            return;
        }
         
        inorderTraverse(root.left, target, k);
         
        if (count &lt; k) {
            minPQ.offer(root.val);
        } else {
            if (Math.abs((double) root.val - target) &lt; Math.abs((double) minPQ.peek() - target)) {
                minPQ.poll();
                minPQ.offer(root.val);
            }
        }
        count++;
         
        inorderTraverse(root.right, target, k);
    }
}

Analysis:
The time complexity would be O(k + (n - k) logk).
Space complexity is O(k).

A time linear solution:

/**
 * 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> closestKValues(TreeNode root, double target, int k) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
         
        Stack<Integer> precedessor = new Stack<>();
        Stack<Integer> successor = new Stack<>();
         
        getPredecessor(root, target, precedessor);
        getSuccessor(root, target, successor);
         
        for (int i = 0; i < k; i++) {
            if (precedessor.isEmpty()) {
                result.add(successor.pop());
            } else if (successor.isEmpty()) {
                result.add(precedessor.pop());
            } else if (Math.abs((double) precedessor.peek() - target) < Math.abs((double) successor.peek() - target)) {
                result.add(precedessor.pop());
            } else {
                result.add(successor.pop());
            }
        }
         
        return result;
    }
     
    private void getPredecessor(TreeNode root, double target, Stack<Integer> precedessor) {
        if (root == null) {
            return;
        }
         
        getPredecessor(root.left, target, precedessor);
         
        if (root.val > target) {
            return;
        }
         
        precedessor.push(root.val);
         
        getPredecessor(root.right, target, precedessor);
    }
     
    private void getSuccessor(TreeNode root, double target, Stack<Integer> successor) {
        if (root == null) {
            return;
        }
         
        getSuccessor(root.right, target, successor);
         
        if (root.val <= target) {
            return;
        }
         
        successor.push(root.val);
         
        getSuccessor(root.left, target, successor);
    }
}

Update on 4/30/19: Time complexity O(k + logn)

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the given BST
     * @param target: the given target
     * @param k: the given k
     * @return: k values in the BST that are closest to the target
     */
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
 
        // step 1: find the closet value and save the path
        Stack<TreeNode> lowerStack = new Stack<>();
        Stack<TreeNode> upperStack = new Stack<>();
 
        TreeNode p = root;
        while (p != null) {
            if (p.val < target) {
                lowerStack.push(p);
                p = p.right;
            } else {
                upperStack.push(p);
                p = p.left;
            }
        }
 
        for (int i = 0; i < k; i++) {
            if (lowerStack.isEmpty()) {
                TreeNode top = upperStack.pop();
                ans.add(top.val);
                goUpperNext(top.right, upperStack);
             
            } else if (upperStack.isEmpty()) {
                TreeNode top = lowerStack.pop();
                ans.add(top.val);
                goLowerNext(top.left, lowerStack);
            } else if (upperStack.peek().val - target <= target - lowerStack.peek().val) {
                TreeNode top = upperStack.pop();
                ans.add(top.val);
                goUpperNext(top.right, upperStack);
            } else if (upperStack.isEmpty() || target - lowerStack.peek().val < upperStack.peek().val - target) {
                TreeNode top = lowerStack.pop();
                ans.add(top.val);
                goLowerNext(top.left, lowerStack);
            }
        }
 
        return ans;
    }
 
    private void goUpperNext(TreeNode node, Stack<TreeNode> stack) {
        TreeNode p = node;
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
    }
 
    private void goLowerNext(TreeNode node, Stack<TreeNode> stack) {
        TreeNode p = node;
        while (p != null) {
            stack.push(p);
            p = p.right;
        }
    }
}

Leetcode: Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

Understand the problem:
This is just an implementation problem. The key is how to separate the list of strings during the serialization process so we can decode the string in the de-serialization process.

One way we can think of is to use the number at front. e.g. abcdef, we can store 6abcdef.
However, what if the string also starts from numbers, e.g. 123abc. In this case, what we stored is 6123abc, which is wrong. Therefore, we need to use another divider to divide the length of the string with the string itself. In this solution, we just use '#'.

One thing needs to be careful in this such kind problem is the length of the string, which is in the form of string, is not a single character. Therefore, we need to parse the string until we see the divider.

Code (Java):

public class Codec {
 
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.size() == 0) {
            return "";
        }
         
        StringBuffer sb = new StringBuffer();
         
        for (String str : strs) {
            int len = str == null ? 0 : str.length();
            sb.append(len);
            sb.append('#');
            sb.append(str);
        }
         
        return sb.toString();
    }
 
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
         
        int i = 0;
        while (i < s.length()) {
            int len = 0;
            // Get length
            while (i < s.length() && s.charAt(i) != '#') {
                len = len * 10 + Character.getNumericValue(s.charAt(i));
                i++;
            }
             
            String str = s.substring(i + 1, i + len + 1);
            result.add(str);
            i = i + len + 1;
        }
         
        return result;
    }
}
 
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

Update on 1/27/15:

public class Codec {
 
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.size() == 0) {
            return "";
        }
        StringBuffer sb = new StringBuffer();
         
        for (String str : strs) {
            if (str == null || str.length() == 0) {
                sb.append("0#");
            } else {
                sb.append(str.length() + "#" + str);
            }
        }
         
        return sb.toString();
    }
 
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> strs = new ArrayList<>();
         
        if (s == null || s.length() == 0) {
            return strs;
        }
         
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && Character.isDigit(s.charAt(j))) {
                j++;
            }
             
            int num = Integer.parseInt(s.substring(i, j));
            i = j;
            i++; // skip '#'
            if (num == 0) {
                strs.add("");
            } else {
                strs.add(s.substring(i, i + num));
            }
             
            i += num;
        }
         
        return strs;
    }
}
 
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs)); 

Leetcode: Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Understand the problem:
The problem can be transformed as a graph problem. We count the in-degree and out-degree for each person. Then find out the person with in-degree n - 1 and out-degree 0.

Code (Java):

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */
 
public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n <= 1) {
            return -1;
        }
         
        int[] inDegree = new int[n];
        int[] outDegree = new int[n];
         
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && knows(i, j)) {
                    outDegree[i]++;
                    inDegree[j]++;
                }
            }
        }
         
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
         
        return -1;
    }
}

Analysis:
Time O(n^2).
Space O(n).

A O(n) time O(1) Space Solution:
Use two pointers, left starts from 0, and right starts from n - 1.
Check if knows(left, right). If yes, left++. Else, right--.
After the first step, we could find out the potential candidate.
In the second step, we validate the candidate by iterating through all the person again. Each one must know the candidate while the candidate must not know anyone else.

Code (Java):

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */
 
public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n <= 1) {
            return -1;
        }
         
        int left = 0;
        int right = n - 1;
         
        // Step 1: Find the potential candidate
        while (left < right) {
            if (knows(left, right)) {
                left++;
            } else {
                right--;
            }
        }
         
        // Step 2: Validate the candidate
        int candidate = right;
        for (int i = 0; i < n; i++) {
            if (i != candidate && (!knows(i, candidate) || knows(candidate, i))) {
                return -1;
            }
        }
         
        return candidate;
    }
}

Leetcode: First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
A binary search problem.

Code (Java):

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */
 
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return 0;
        }
         
        int lo = 1;
        int hi = n;
         
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
             
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
         
        if (isBadVersion(lo)) {
            return lo;
        }
         
        if (isBadVersion(hi)) {
            return hi;
        }
         
        return 0;
    }
}

Update on 10/24/15:
We use long instead of int to avoid the integer overflow problem.

Code (Java):

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */
 
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return 0;
        }
         
        long lo = 1;
        long hi = n;
         
        while (lo + 1 < hi) {
            long mid = lo + (hi - lo) / 2;
            boolean bad = isBadVersion((int) mid);
            if (bad) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
         
        if (isBadVersion((int) lo)) {
            return (int) lo;
        }
         
        if (isBadVersion((int) hi)) {
            return (int) hi;
        }
         
        return 0;
    }
}

Update on 1/26/15:

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */
 
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if (n <= 0) {
            return -1;
        }
         
        int lo = 1;
        int hi = n;
         
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
         
        if (isBadVersion(lo)) {
            return lo;
        }
         
        return -1;
    }
}

Leetcode: Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

Code (Java):

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

public class Solution {
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
         
        Map<Integer, String> map = new HashMap<>();
        // Step 1: fill the hash map
        fillHashMap(map);
     
        StringBuffer sb = new StringBuffer();
        int groupId = 1;
         
        // Step 2: group the num with 3 digits
        while (num > 0) {
            int group = num % 1000;
             
            if (groupId > 1 && group > 0) {
                String groupStr = getGroupName(groupId);
                sb.insert(0, groupStr);
            }
             
            String str = numberToWordsHelper(group, map);
            sb.insert(0, str);
             
            groupId++;
            num /= 1000;
        }
         
        String result = sb.toString();
        if (result.charAt(result.length() - 1) == ' ') {
            return result.substring(0, result.length() - 1);
        } else {
            return result;
        }
    }
     
    private void fillHashMap(Map<Integer, String> map) {
        map.put(1, "One ");
        map.put(2, "Two ");
        map.put(3, "Three ");
        map.put(4, "Four ");
        map.put(5, "Five ");
        map.put(6, "Six ");
        map.put(7, "Seven ");
        map.put(8, "Eight ");
        map.put(9, "Nine ");
        map.put(10, "Ten ");
        map.put(11, "Eleven ");
        map.put(12, "Twelve ");
        map.put(13, "Thirteen ");
        map.put(14, "Fourteen ");
        map.put(15, "Fifteen ");
        map.put(16, "Sixteen ");
        map.put(17, "Seventeen ");
        map.put(18, "Eighteen ");
        map.put(19, "Nineteen ");
        map.put(20, "Twenty ");
        map.put(30, "Thirty ");
        map.put(40, "Forty ");
        map.put(50, "Fifty ");
        map.put(60, "Sixty ");
        map.put(70, "Seventy ");
        map.put(80, "Eighty ");
        map.put(90, "Ninety ");
        map.put(100, "One Hundred ");
        map.put(1000, "One Thousand ");
    }
     
    private String getGroupName(int groupId) {
        String result = null;
        switch(groupId) {
            case 2: result = "Thousand ";
            break;
             
            case 3: result = "Million ";
            break;
             
            case 4: result = "Billion ";
            break;
        }
         
        return result;
    }
     
    private String numberToWordsHelper(int num, Map<Integer, String> map) {
        int pos = 0;
        StringBuffer sb = new StringBuffer();
         
        if (num <= 0) {
            return "";
        }
         
        int tmp = num;
        while (tmp > 0) {
            pos++;
            tmp /= 10;
        }
         
        while (num > 0) {
            if (num <= 20) {
                sb.append(map.get(num));
                break;
            }
             
            int digit = num / (int) Math.pow(10, pos - 1);
            int curr = digit * (int) Math.pow(10, pos - 1);
             
            if (pos == 3) {
                sb.append(map.get(digit));
                sb.append("Hundred ");
            } else {
                sb.append(map.get(curr));
            }
             
            num = num % (int) Math.pow(10, pos - 1);
            pos--;
        }
         
        return sb.toString();
    }
}

A neat solution without using HashMap.

public class Solution {
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
         
        String[] group = {"", "Thousand ", "Million ", "Billion "};
        String[] dict1 = {"", "One ", "Two ", "Three ", "Four ", 
                          "Five ", "Six ", "Seven ", "Eight ", "Nine ",
                          "Ten ", "Eleven ", "Twelve ", "Thirteen ",
                          "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ",
                          "Eighteen ", "Nineteen "};
        String[] dict2 = {"", "", "Twenty ", "Thirty ", "Forty ", "Fifty ",
                          "Sixty ", "Seventy ", "Eighty ", "Ninety "};
         
        StringBuffer sb = new StringBuffer();
         
        for (int i = 0; i < 4; i++) {
            int curr = num % 1000;
            if (curr > 0) {
                if (i > 0) {
                    sb.insert(0, group[i]);
                }
                sb.insert(0, numToWordsHelper(curr, dict1, dict2));
            }
            num /= 1000;
        }
         
        String result = sb.toString();
        if (result.charAt(result.length() - 1) == ' ') {
            return result.substring(0, result.length() - 1);
        } else {
            return result;
        }
    }
     
    private String numToWordsHelper(int num, String[] dict1, String[] dict2) {
        StringBuffer result = new StringBuffer();
         
        int a = num / 100;
        int b = num % 100;
        int c = num % 10;
         
        if (a > 0) {
            result.append(dict1[a] + "Hundred ");
        }
         
        if (b > 0 && b < 20) {
            result.append(dict1[b]);
            c = 0; 
        } else if (b >= 20) {
            b /= 10;
            result.append(dict2[b]);
        }
         
        if (c > 0) {
            result.append(dict1[c]);
        }
         
        return result.toString();
    }
}

Summary:
There are some corner cases need to be very careful:
input = 1000, output = One Thousand, not One Thousand Zero
input = 1,000,000, output is One million , not One Million Thousand.