Leetcode: 348. Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves is allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

Hint:

1. Could you trade extra space such that move() operation can be done in O(1)?
2. You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

Solution:
Use addtional arrays rows[n], cols[n] and two varialbes diagonal, anti_diagonal to mark the number of Xs and Os. 

Code (Java):

public class TicTacToe {
    private int[][] rows;
    private int[][] cols;
    private int[] diag;
    private int[] xdiag;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
        rows = new int[2][n];
        cols = new int[2][n];
        diag = new int[2];
        xdiag = new int[2];
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int p = player == 1 ? 0 : 1;
        
        rows[p][row]++;
        cols[p][col]++;
        
        if (row == col) {
            diag[p]++;
        }
            
        // X-diagonal
        if (row + col == n - 1) {
            xdiag[p]++;
        }
            
        // If any of them equals to n, return 1
        if (rows[p][row] == n || cols[p][col] == n || 
            diag[p] == n || xdiag[p] == n) {
            return p + 1;
        }
        
        return 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

A Neat Code:
In the previous solution, we allocate two arrays for player 1 and 2, respectively. Actually we can use only one array for both of the players. Say, if it is player 1 put one chess, add that location by 1. If it is player 2, deduce it by one. Finally, if either player 1 or player 2 win, that location must be equal to n or -n. 

Code (Java):

public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diag;
    private int xdiag;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
        diag = 0;
        xdiag = 0;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int count = player == 1 ? 1 : -1;
        
        rows[row] += count;
        cols[col] += count;
        
        if (row == col) {
            diag += count;
        }
            
        // X-diagonal
        if (row + col == n - 1) {
            xdiag += count;
        }
            
        // If any of them equals to n, return 1
        if (Math.abs(rows[row]) == n || 
            Math.abs(cols[col]) == n || 
            Math.abs(diag) == n || 
            Math.abs(xdiag) == n) {
            return count > 0 ? 1 : 2;
        }
        
        return 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

Leetcode: Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Code (Java):

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0;
        int j = 0;
        
        List<Integer> result = new ArrayList<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                if (result.isEmpty() || nums1[i] != result.get(result.size() - 1)) {
                    result.add(nums1[i]);
                }
                i++;
                j++;
            }
        }
        
        return listToArray(result);
    }
    
    private int[] listToArray(List<Integer> list) {
        int[] result = new int[list.size()];
        
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        
        return result;
    }
}

Leetcode: Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to num2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution 1:
Sort the two arrays and iterate over to find out the intersections. So the overall time complexity is bounded by O(n logn), where n is the length of the longer array. The main body of the loop is bounded by O(m + n). 

Code (Java):

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        
        int i = 0;
        int j = 0;
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        List<Integer> result = new ArrayList<>();
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                result.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]){
                i++;
            } else {
                j++;
            }
        }
        
        // Convert list to array
        return listToArray(result);
    }
    
    private int[] listToArray(List<Integer> list) {
        int[] result = new int[list.size()];
        
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        
        return result;
    }
}

Solution 2:
Use a HashMap to store the first array, then check each element of the second array and see if it is in the map. Note that since we need to output all repeated elements, we also need to count the occurrence of each array element in the map, and consume it when we compare with the second array.

Code (Java):

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        // step1: Put elements in nums1 into the map
        for (int num : nums1) {
            if (map.containsKey(num)) {
                int freq = map.get(num);
                map.put(num, freq + 1);
            } else {
                map.put(num, 1);
            }
        }
        
        // step 2: iterate the nums2 and get the result
        List<Integer> result = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num) && map.get(num) > 0) {
                result.add(num);
                int freq = map.get(num);
                freq--;
                map.put(num, freq);
            }
        }
        
        return listToArray(result);
    }
    
    private int[] listToArray(List<Integer> list) {
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        
        return result;
    }
}

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• Solution 1, i.e., sorting,  would be better since it does not need extra memory. 
• What if nums1's size is small compared to num2's size? Which algorithm is better?
• If two arrays are sorted, we could use binary search, i.e., for each element in the shorter array, search in the longer one. So the overall time complexity is O(nlogm), where n is the length of the shorter array, and m is the length of the longer array. Note that this is better than Solution 1 since the time complexity is O(n + m) in the worst case. 
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
• If the two arrays have relatively the same length, we can use external sort to sort out the two arrays in the disk. Then load chunks of each array into the memory and compare, by using the method 1. 
• If one array is too short while the other is long, in this case, if memory is limited and nums2 is stored in disk, partition it and send portions of nums2 piece by piece. keep a pointer for nums1 indicating the current position, and it should be working fine~
• Another method is, store the larger array into disk, and for each element in the shorter array, use "Exponential Search" and search in the longer array. 

Leetcode: Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Understand the problem:
https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst

Every node will maintain a val sum recording the total of number on it's left bottom side, dupcounts the duplication. For example, [3, 2, 2, 6, 1], from back to beginning,we would have:

                1(0, 1)
                     \
                     6(3, 1)
                     /
                   2(0, 2)
                       \
                        3(0, 1)

When we try to insert a number, the total number of smaller number would be adding dup and sum of the nodes where we turn right. for example, if we insert 5, it should be inserted on the way down to the right of 3, the nodes where we turn right is 1(0,1), 2,(0,2), 3(0,1), so the answer should be (0 + 1)+(0 + 2)+ (0 + 1) = 4

if we insert 7, the right-turning nodes are 1(0,1), 6(3,1), so answer should be (0 + 1) + (3 + 1) = 5

Code (Java):

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        Integer[] result = new Integer[nums.length];
        
        BSTNode root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(root, nums[i], i, result, 0);
        }
        
        return Arrays.asList(result);
    }
    
    private BSTNode insert(BSTNode root, int num, int i, Integer[] result, 
                           int preSum) {
        if (root == null) {
            root = new BSTNode(num, 0);
            result[i] = preSum;
            return root;
        } else if (root.val == num) {
            root.dup++;
            result[i] = preSum + root.numOfLeftNodes;
            return root;
        } else if (root.val > num) {
            root.numOfLeftNodes++;
            root.left = insert(root.left, num, i, result, preSum);
        } else {
            root.right = insert(root.right, num, i, result, 
                preSum + root.numOfLeftNodes + root.dup);
        }
        
        return root;
    }
    
    class BSTNode {
        int val;
        int dup = 1;
        int numOfLeftNodes;
        BSTNode left, right;
        
        BSTNode(int val, int numOfLeftNodes) {
            this.val = val;
            this.numOfLeftNodes = numOfLeftNodes;
        }
    }
}

Leetcode: Shortest Distance from All Buildings

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

• Each 0 marks an empty land which you can pass by freely.
• Each 1 marks a building which you cannot pass through.
• Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Understand the problem:
A BFS problem. Search from each building and calculate the distance to the building. One thing to note is an empty land must be reachable by all buildings. To achieve this, maintain an array of counters. Each time we reach a empty land from a building, increase the counter. Finally, a reachable point must have the counter equaling to the number of buildings. 

Code (Java):

public class Solution {
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dist = new int[m][n];
        int[][] reach = new int[m][n];
        // step 1: BFS and calcualte the min dist from each building
        int numBuildings = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    boolean[][] visited = new boolean[m][n];
                    Queue<Integer> queue = new LinkedList<>();
                    shortestDistanceHelper(i, j, 0, dist, reach, grid, visited, queue);
                    numBuildings++;
                }
            }
        }
        
        // step 2: caluclate the minimum distance
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && reach[i][j] == numBuildings) {
                    minDist = Math.min(minDist, dist[i][j]);
                }
            }
        }
        
        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }
    
    private void shortestDistanceHelper(int x, int y, int currDist, 
                                        int[][] dist, int[][] reach, int[][] grid,
                                        boolean[][] visited, Queue<Integer> queue) {
        fill(x, y, x, y, currDist, dist, reach, grid, visited, queue);
        
        int m = grid.length;
        int n = grid[0].length;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            currDist++;
            for (int sz = 0; sz < size; sz++) {
                int cord = queue.poll();
                int i = cord / n;
                int j = cord % n;
                
                fill(x, y, i - 1, j, currDist, dist, reach, grid, visited, queue);
                fill(x, y, i + 1, j, currDist, dist, reach, grid, visited, queue);
                fill(x, y, i, j - 1, currDist, dist, reach, grid, visited, queue);
                fill(x, y, i, j + 1, currDist, dist, reach, grid, visited, queue);
            }

        }
    }
    
    private void fill(int origX, int origY, int x, int y, int currDist, 
                      int[][] dist, int[][] reach,  
                      int[][] grid, boolean[][] visited, Queue<Integer> queue) {
        
        int m = dist.length;
        int n = dist[0].length;
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
            return;
        }
        
        if ((x != origX || y != origY) && grid[x][y] != 0) {
            return;
        }
        
        visited[x][y] = true;
        
        dist[x][y] += currDist;
        reach[x][y]++;
        
        queue.offer(x * n + y);
    }
}

Update on 6/20/16:

public class Solution {
    private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] reach = new int[m][n];
        int[][] distance = new int[m][n];
        int numBuildings = 0;
        Queue<Integer> queue = new LinkedList<>();
        
        // Find the minimum distance from all buildings
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    boolean[][] visited = new boolean[m][n];
                    shortestDistanceHelper(i, j, 0, grid, reach, distance, visited, queue);
                    numBuildings++;
                }
            }
        }
        
        // step 2: check the min distance reachable by all buildings
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && reach[i][j] == numBuildings && distance[i][j] < minDistance) {
                    minDistance = distance[i][j];
                }
            }
        }
        
        if (minDistance == Integer.MAX_VALUE) {
            return -1;
        } else {
            return minDistance;
        }
    }
    
    private void shortestDistanceHelper(int row, int col, int dist, int[][] grid, 
                                        int[][] reach, int[][] minDistance, 
                                        boolean[][] visited, Queue<Integer> queue) {
        fill(row, col, dist, grid, reach, minDistance, visited, queue);
        
        int n = grid[0].length;
        
        while (!queue.isEmpty()) {
            dist++;
            int sz = queue.size();
            for (int j = 0; j < sz; j++) {
                int cord = queue.poll();
                int x = cord / n;
                int y = cord % n;
                for (int i = 0; i < 4; i++) {
                    fill(dir[i][0] + x, dir[i][1] + y, dist, grid, reach, minDistance, visited, queue);
                }
            }
        }
    }
    
    private void fill(int row, int col, int dist, int[][] grid, int[][] reach, int[][] minDistance, 
                      boolean[][] visited, Queue<Integer> queue) {
        int m = grid.length;
        int n = grid[0].length;
        
        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] || grid[row][col] == 2) {
            return;
        }          
        
        // We need to handle the starting building separtately
        if (dist != 0 && grid[row][col] == 1) {
            return;
        }
        
        visited[row][col] = true;
        minDistance[row][col] += dist;
        reach[row][col] += 1;
        
        queue.offer(row * n + col);
        
    }
}

Discussion:
1. Be very careful when to accumulate the distance by 1. It should be after visiting all the current node's neighbors. 

Leetcode: Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

Understand the problem:
https://leetcode.com/discuss/69572/easiest-java-solution-with-explanations

This is a basic union-find problem. Given a graph with points being added, we can at least solve:

1. How many islands in total?
2. Which island is pointA belonging to?
3. Are pointA and pointB connected?

The idea is simple. To represent a list of islands, we use trees. i.e., a list of roots. This helps us find the identifier of an island faster. If roots[c] = p means the parent of node c is p, we can climb up the parent chain to find out the identifier of an island, i.e., which island this point belongs to:

Do root[root[roots[c]]]... until root[c] == c;

To transform the two dimension problem into the classic UF, perform a linear mapping:

int id = n * x + y;

Initially assume every cell are in non-island set {-1}. When point A is added, we create a new root, i.e., a new island. Then, check if any of its 4 neighbors belong to the same island. If not,union the neighbor by setting the root to be the same. Remember to skip non-island cells.

UNION operation is only changing the root parent so the running time is O(1).

FIND operation is proportional to the depth of the tree. If N is the number of points added, the average running time is O(logN), and a sequence of 4N operations take O(NlogN). If there is no balancing, the worse case could be O(N^2).

Remember that one island could have different roots[node] value for each node. Becauseroots[node] is the parent of the node, not the highest root of the island. To find the actually root, we have to climb up the tree by calling findIsland function.

Here I've attached my solution. There can be at least two improvements: union by rank & pass compression. However I suggest first finish the basis, then discuss the improvements.

Code (Java):

public class Solution {
    private int top;
    private int bottom;
    private int left;
    private int right;
    private int area = 0;
    
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0) {
            return 0;
        }
        
        this.top = y;
        this.bottom = y;
        this.left = x;
        this.right = x;
        
        int m = image.length;
        int n = image[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        minAreaHelper(image, x, y, visited);
        
        return area;
    }
    
    private void minAreaHelper(char[][] image, int x, int y, 
                               boolean[][] visited) {
        int m = image.length;
        int n = image[0].length;
        
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
            return;
        }          
        
        if (image[x][y] == '0') {
            return;
        }
        
        visited[x][y] = true;
        
        // update the border 
        top = Math.min(top, y);
        bottom = Math.max(bottom, y);
        left = Math.min(left, x);
        right = Math.max(right, x);
        
        int curArea = (bottom - top + 1) * (right - left + 1);
        area = Math.max(area, curArea);
        
        minAreaHelper(image, x, y - 1, visited);
        minAreaHelper(image, x, y + 1, visited);
        minAreaHelper(image, x - 1, y, visited);
        minAreaHelper(image, x + 1, y, visited);
    }
}

Leetcode: Smallest Rectangle Enclosing Black Pixels

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
  "0010",
  "0110",
  "0100"
]

and x = 0, y = 2,

Return 6.

DFS Solution:
Look for the borders for the black pixels. 

Code (Java):

public class Solution {
    private int top;
    private int bottom;
    private int left;
    private int right;
    private int area = 0;
    
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0) {
            return 0;
        }
        
        this.top = y;
        this.bottom = y;
        this.left = x;
        this.right = x;
        
        int m = image.length;
        int n = image[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        minAreaHelper(image, x, y, visited);
        
        return area;
    }
    
    private void minAreaHelper(char[][] image, int x, int y, 
                               boolean[][] visited) {
        int m = image.length;
        int n = image[0].length;
        
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
            return;
        }          
        
        if (image[x][y] == '0') {
            return;
        }
        
        visited[x][y] = true;
        
        // update the border 
        top = Math.min(top, y);
        bottom = Math.max(bottom, y);
        left = Math.min(left, x);
        right = Math.max(right, x);
        
        int curArea = (bottom - top + 1) * (right - left + 1);
        area = Math.max(area, curArea);
        
        minAreaHelper(image, x, y - 1, visited);
        minAreaHelper(image, x, y + 1, visited);
        minAreaHelper(image, x - 1, y, visited);
        minAreaHelper(image, x + 1, y, visited);
    }
}

Update on 4/2/19:

public class Solution {
    /**
     * @param image: a binary matrix with '0' and '1'
     * @param x: the location of one of the black pixels
     * @param y: the location of one of the black pixels
     * @return: an integer
     */
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0) {
            return 0;
        }

        int m = image.length;
        int n = image[0].length;

        int left = findLeft(image, 0, y);
        int right = findRight(image, y, n - 1);
        int top = findTop(image, 0, x);
        int bottom = findBottom(image, x, m - 1);

        return (right - left + 1) * (bottom - top + 1);
    }

    private int findLeft(char[][] image, int lo, int hi) {
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isEmptyColumn(image, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        if (!isEmptyColumn(image, lo)) {
            return lo;
        }

        return hi;
    }

    private int findRight(char[][] image, int lo, int hi) {
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isEmptyColumn(image, mid)) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }

        if (!isEmptyColumn(image, hi)) {
            return hi;
        }
        return lo;
    }

    private int findTop(char[][] image, int lo, int hi) {
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isEmptyRow(image, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        if (!isEmptyRow(image, lo)) {
            return lo;
        }

        return hi;
    }

    private int findBottom(char[][] image, int lo, int hi) {
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;

            if (isEmptyRow(image, mid)) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }

        if (!isEmptyRow(image, hi)) {
            return hi;
        }

        return lo;
    }

    private boolean isEmptyColumn(char[][] image, int col) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][col] == '1') {
                return false;
            }
        }

        return true;
    }

    private boolean isEmptyRow(char[][] image, int row) {
        for (int i = 0; i < image[0].length; i++) {
            if (image[row][i] == '1') {
                return false;
            }
        }

        return true;
    }
}

Complexity:
O(mlogn + nlogm)

Leetcode: Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

Understand the problem:
The problem is a backpack problem. Each item can be selected unlimited number of times. Ask what is the minimum picks in order to fulfill the target amount. We can solve it using DP. 

-- dp[n + 1][amount + 1], where dp[i][j] means the minimum number of coins in the first i coins for which the sum of amount equal to j. 
-- Initialization: 
dp[0][0] = 0;
dp[0][j] = Integer.MAX_VALUE, means there is no way to fulfill the amount j with no coins 
dp[i][0] = 0, meaning the number of coins is 0 to meet the total amount 0. 
For others, the initial state is Integer.MAX_VALUE. 

Code (Java):

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount <= 0) {
            return 0;
        }
        
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        
        // initilization
        for (int i = 1; i <= amount; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k * coins[i - 1] <= j; k++) {
                    if (dp[i - 1][j - k * coins[i - 1]] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], 
                          dp[i - 1][j - k * coins[i - 1]] + k);
                    }
                }
            }
        }
        
        if (dp[n][amount] == Integer.MAX_VALUE) {
            return -1;
        } else {
            return dp[n][amount];
        }
    }
}

A O(amount) space solution:
Since dp[i] only depends on dp[i - 1], we can simply reduce the space complexity to O(amount). 

Code (Java):

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount <= 0) {
            return 0;
        }
        
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    if (dp[i - coins[j]] != Integer.MAX_VALUE) {
                        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                    }
                }
            }
        }
        
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        } else {
            return dp[amount];
        }
    }
} 

Leetcode: Wiggle Sort II

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

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

Understand the problem:
The mainly difference between Wiggle sort I and II is this question asks for nums[even] < nums[odd], not nums[even] <= nums[odd]. So If we still use the greedy solution, it may not find out a valid solution. 

An O(nlogn) time solution, out-of-place:
We can first sort the array, then partition the array into two halves. So all elements in the first half is less than the second half. Then we can pick up one element from each half from the end, and form the solution . e.g. 
nums = [1, 3, 2, 2, 3, 1]. 

After the sorting, the array becomes [1, 1, 2, 2, 3, 3]. Then we partition the array into two halves, the left half is [1, 1, 2]. The right half is [2, 3, 3]. Then we pick up one element from each and form the solution.
[1, 1, 2]            [2, 3, 3]
         |                        |
       left                    right
2, 3, 1, 3, 1, 2

Since there must be a solution, the left element we choose each time must be less than the right element (why ? because if the left is equal to the right, all elements before right and after left must be equal as well, so there will be no solution existed). 

Note that if there are odd number of elements, the left half must be 1 more than the right, not reverse. That is because the last element must be indexed as even (e.g. 0, 1, 2, 3, 4, 5, 6), and since nums[even] < nums[odd], so the last number must be in the smaller half. 


Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        Arrays.sort(nums);
        int n = nums.length;
        
        int[] temp = new int[n];
        int left = (n - 1) / 2;
        int right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                temp[i] = nums[left];
                left--;
            } else {
                temp[i] = nums[right];
                right--;
            }
        }
        
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

A wrong solution:

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        Arrays.sort(nums);
        int n = nums.length;
        
        int[] temp = new int[n];
        int left = 0;
        int right = (n + 1) / 2;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                temp[i] = nums[left];
                left++;
            } else {
                temp[i] = nums[right];
                right++;
            }
        }
        
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

Why the solution is wrong?

Input:[4,5,5,6]

Output:[4,5,5,6]

That is mainly because although the 4 must be less than 5 for the first two elements in the result, there is no guarantee that the third element must be less than the second element.  

A O(n) time, out-of-place solution:
We can use a quick select algorithm to find out the median of the array, so the first half is less than the second half. 

Note that we must do a 3-way partition before doing the wiggle sort. That is, we need to put all elements less than the median into the left, all median elements in the middle, and all element greater than the median into the right. This can guarantee that  while each time we pick up an element on the left and right half, they are absolutely not equal. 

Code (Java):

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int n = nums.length;
        
        // Step 1: Find median of the array, return the index of the median
        int median = findMedian(nums, 0, n - 1, (n - 1) / 2);
        
        // Step 2: 3-way sort, put median in the middle, 
        // numbers less than median on the left, 
        // numbers greater than median on the right
        int[] temp = new int[n];
        int left = 0;
        int right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[median]) {
                temp[left] = nums[i];
                left++;
            } else if (nums[i] > nums[median]) {
                temp[right] = nums[i];
                right--;
            }
        }
        
        // add median into the middle
        for (int i = left; i <= right; i++) {
            temp[i] = nums[median];
        }
        
        // Step 3: wiggle sort
        left = (n - 1) / 2;
        right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                nums[i] = temp[left];
                left--;
            } else {
                nums[i] = temp[right];
                right--;
            }
        }
    }
    
    private int findMedian(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return lo;
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return pivot;
        }
        
        if (pivot > k) {
            return findMedian(nums, lo, pivot - 1, k);
        } else {
            return findMedian(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Alternative solution using in-place 3-way partition:

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        
        int n = nums.length;
        
        // Step 1: Find median of the array, return the index of the median
        int median = findMedian(nums, 0, n - 1, (n - 1) / 2);
        
        // Step 2: 3-way partition, put median in the middle, 
        // numbers less than median on the left, 
        // numbers greater than median on the right
        int left = 0;
        int right = n - 1;
        int j = 0;
        while (j <= right) {
            if (nums[j] < nums[median]) {
                swap(nums, j, left);
                j++;
                left++;
            } else if (nums[j] > nums[median]) {
                swap(nums, j, right);
                right--;
            } else {
                j++;
            }
        }
        
        int[] temp = new int[n];
        System.arraycopy(nums, 0, temp, 0, n);
        
        // Step 3: wiggle sort
        left = (n - 1) / 2;
        right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                nums[i] = temp[left];
                left--;
            } else {
                nums[i] = temp[right];
                right--;
            }
        }
    }
    
    private int findMedian(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return lo;
        }
        
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return pivot;
        }
        
        if (pivot > k) {
            return findMedian(nums, lo, pivot - 1, k);
        } else {
            return findMedian(nums, pivot + 1, hi, k);
        }
    }
    
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
        
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            
            if (i <= j) {
                swap(nums, i, j);
            }
        }
        
        swap(nums, lo, j);
        
        return j;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Update on 5/20/19:

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: nothing
     */
    public void wiggleSort(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return;
        }
        
        // step 1: find meadian of the array
        int median = findMedian(nums);
        
        // step 2: 3-way partition
        threeWayPartition(nums, median);
        
        // step 3: inter-leave the array
        int[] temp = new int[nums.length];
        int left = (nums.length - 1) / 2;
        int right = nums.length - 1;
        
        for (int i = 0; i < nums.length; i += 2) {
            temp[i] = nums[left];
            left--;
            
            if (right > (nums.length - 1) / 2) {
                temp[i + 1] = nums[right];
                right--;
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }
    
    private int findMedian(int[] nums) {
        return findMedianHelper(nums, 0, nums.length - 1, (nums.length - 1) / 2);
    }
    
    private int findMedianHelper(int[] nums, int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
         
        int i = start;
        int j = end;
        int pivot = nums[(i + j) / 2];
         
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
             
            while (i <= j && nums[j] > pivot) {
                j--;
            }
             
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
         
        if (k <= j) {
            return findMedianHelper(nums, start, j, k);
        } else if (k >= i) {
            return findMedianHelper(nums, i, end, k);
        } else {
            return nums[k];
        }
    }
    
    private void threeWayPartition(int[] nums, int median) {
        int start = 0;
        int end = nums.length - 1;
        int j = 0;
        
        while (j <= end) {
            if (nums[j] < median) {
                swap(nums, start, j);
                start++;
                j++;
            } else if (nums[j] > median) {
                swap(nums, end, j);
                end--;
            } else {
                j++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Leetcode: Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

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

Understand the problem:
The problem is a little bit ambiguous.  The two words used to calculate the product of length must not share any common characters. e.g. word1 = abc, word2 = bcd, the product is 0 not 1, because they share common chars. 

The most straight-forward way to solve this problem is to pick up any two words, and check if they have common characters. If not, then calculate the maximum product of the length. 

Now let's analyze the complexity in time. Suppose the number of words is n, and average word length is m. So the time complexity for the  brute-force solution is O(n^2 * m). 

A better approach using bit manipulation:
Now let's think can we reduce the time complexity when we check the intersection of two words? 

Since each word contains 26 characters in lower case only. We can use a bit map to encode the string. Since we only need 26 bits for a word, it is enough to use an integer to encode a string. 

Code (Java):

public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length <= 1) {
            return 0;
        }
        
        int n = words.length;
        int[] encodedWords = new int[n];
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                encodedWords[i] |= (1 << (c - 'a'));
            }
        }
        
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((encodedWords[i] & encodedWords[j]) == 0) {
                    maxLen = Math.max(maxLen, 
                        words[i].length() * words[j].length());
                }
            }
        }
        
        return maxLen;
    }
}

Analysis:
Compared to the brute force solution, the time complexity of the bit solution is O(26 * n^2), which is O(n^2). If m >> 26, the bit solution is better.