Wednesday, January 13, 2016

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



Tuesday, January 12, 2016

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 01 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 = 3positions = [[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 = 0y = 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)

Monday, January 11, 2016

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

Sunday, January 10, 2016

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. 

Saturday, January 9, 2016

Leetcode: 326. Power of Three

Given an integer, write a function to determine if it is a power of three.
Follow up:
Could you do it without using any loop / recursion?
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Brute-force Solution:
The problem asks for if there is a number n, where n = 3^x. So the brute-force solution is to try each x from 0 and see if 3^x is equal to n, until 3^x is greater than n then we return false.

Code (Java):
public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        
        int i = 0;
        long cur = (long) Math.pow(3, i);
        long longN = (long) n;
        
        while (cur <= longN) {
            if (cur == longN) {
                return true;
            }
            
            i++;
            cur = (long) Math.pow(3, i);
        }
        
        return false;
    }
}

Some tricky solutions:
Method 2
If log10(n) / log10(3) returns an int (more precisely, a double but has 0 after decimal point), then n is a power of 3. (original post). But be careful here, you cannot use log (natural log) here, because it will generate round off error for n=243. This is more like a coincidence. I mean whenn=243, we have the following results:
log(243) = 5.493061443340548    log(3) = 1.0986122886681098
   ==> log(243)/log(3) = 4.999999999999999

log10(243) = 2.385606273598312    log10(3) = 0.47712125471966244
   ==> log10(243)/log10(3) = 5.0
This happens because log(3) is actually slightly larger than its true value due to round off, which makes the ratio smaller.
public boolean isPowerOfThree(int n) {
    return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}










Editional Soluton:

Solution

In this article we will look into ways of speeding up simple computations and why that is useful in practice.

Approach #1 Loop Iteration [Accepted]

One simple way of finding out if a number n is a power of a number b is to keep dividing n by b as long as the remainder is 0. This is because we can write
n=bxn=b×b××b

Hence it should be possible to divide n by b x times, every time with a remainder of 0 and the end result to be 1.
Java
public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;    
    }
}
Notice that we need a guard to check that n != 0, otherwise the while loop will never finish. For negative numbers, the algorithm does not make sense, so we will include this guard as well.
Complexity Analysis
  • Time complexity : O(log_b(n)). In our case that is O(log_3n). The number of divisions is given by that logarithm.
  • Space complexity : O(1). We are not using any additional memory.

Approach #2 Base Conversion [Accepted]

In Base 10, all powers of 10 start with the digit 1 and then are followed only by 0 (e.g. 10, 100, 1000). This is true for other bases and their respective powers. For instance in base 2, the representations of 10_2100_2 and 1000_2 are 2_{10}4_{10} and 8_{10} respectively. Therefore if we convert our number to base 3 and the representation is of the form 100...0, then the number is a power of 3.
Proof
Given the base 3 representation of a number as the array s, with the least significant digit on index 0, the formula for converting from base 3 to base 10 is:
\sum_{i=0}^{len(s) - 1} s[i] * 3^{i}

Therefore, having just one digit of 1 and everything else 0 means the number is a power of 3.
Implementation
All we need to do is convert [4] the number to base 3 and check if it is written as a leading 1 followed by all 0.
A couple of built-in Java functions will help us along the way.
String baseChange = Integer.toString(number, base);
The code above converts number into base base and returns the result as a String. For example, Integer.toString(5, 2) == "101" andInteger.toString(5, 3) == "12".
boolean matches = myString.matches("123");
The code above checks if a certain Regular Expression[2] pattern exists inside a string. For instance the above will return true if the substring "123" exists inside the string myString.
boolean powerOfThree = baseChange.matches("^10*$")
We will use the regular expression above for checking if the string starts with 1 ^1, is followed by zero or more 00* and contains nothing else $.
Java
public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}
Complexity Analysis
  • Time complexity : O(log_3n).
    Assumptions:
    • Integer.toString() - Base conversion is generally implemented as a repeated division. The complexity of should be similar to our approach #1:O(log_3n).
    • String.matches() - Method iterates over the entire string. The number of digits in the base 3 representation of n is O(log_3n).
  • Space complexity : O(log_3n).
    We are using two additional variables,
    • The string of the base 3 representation of the number (size log_3n)
    • The string of the regular expression (constant size)

Approach #3 Mathematics [Accepted]

We can use mathematics as follows
n=3ii=log3(n)i=logb(n)logb(3)

n is a power of three if and only if i is an integer. In Java, we check if a number is an integer by taking the decimal part (using % 1) and checking if it is 0.
Java
public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}
Common pitfalls
This solution is problematic because we start using doubles, which means we are subject to precision errors. This means, we should never use == when comparing doubles. That is because the result of Math.log10(n) / Math.log10(3) could be 5.0000001 or 4.9999999. This effect can be observed by using the function Math.log() instead of Math.log10().
In order to fix that, we need to compare the result against an epsilon.
Java
return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
Complexity Analysis
  • Time complexity : Unknown The expensive operation here is Math.log, which upper bounds the time complexity of our algorithm. The implementation is dependent on the language we are using and the compiler[3]
  • Space complexity : O(1). We are not using any additional memory. The epsilon variable can be inlined.

Approach #4 Integer Limitations [Accepted]

An important piece of information can be deduced from the function signature
public boolean isPowerOfThree(int n)
In particular, n is of type int. In Java, this means it is a 4 byte, signed integer [ref]. The maximum value of this data type is 2147483647. Three ways of calculating this value are
  • Google
  • System.out.println(Integer.MAX_VALUE);
  • MaxInt = \frac{ 2^{32} }{2} - 1 since we use 32 bits to represent the number, half of the range is used for negative numbers and 0 is part of the positive numbers
Knowing the limitation of n, we can now deduce that the maximum value of n that is also a power of three is 1162261467. We calculate this as:
3^{\lfloor{}log_3{MaxInt}\rfloor{}} = 3^{\lfloor{}19.56\rfloor{}} = 3^{19} = 1162261467

Therefore, the possible values of n where we should return true are 3^03^1 ... 3^{19}. Since 3 is a prime number, the only divisors of 3^{19} are 3^03^1 ... 3^{19}, therefore all we need to do is divide 3^{19} by n. A remainder of 0 means n is a divisor of 3^{19} and therefore a power of three.
Java
public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}
Complexity Analysis
  • Time complexity : O(1). We are only doing one operation.
  • Space complexity : O(1). We are not using any additional memory.

Performance Measurements

Single runs of the function make it is hard to accurately measure the difference of the two solutions. On LeetCode, on the Accepted Solutions Runtime Distribution page, all solutions being between 15 ms and 20 ms. For completeness, we have proposed the following benchmark to see how the two solutions differ.
Java Benchmark Code
public static void main(String[] args) {
    Solution sol = new Solution();
    int iterations = 1; // See table header for this value
    for (int i = 0; i < iterations; i++) {
        sol.isPowerOfThree(i);
    }
}
In the table below, the values are in seconds.
Iterations10^610^710^810^9Maxint
Java Approach #1 (Naive)0.040.070.302.475.26
Java Approach #2 (Strings)0.684.0238.90409.16893.89
Java Approach #3 (Logarithms)0.090.504.5945.5397.50
Java Approach #4 (Fast)0.040.060.080.410.78
As we can see, for small values of N, the difference is not noticeable, but as we do more iterations and the values of n passed to isPowerOfThree() grow, we see significant boosts in performance for Approach #4.

Conclusion

Simple optimizations like this might seem negligible, but historically, when computation power was an issue, it allowed certain computer programs (such as Quake 3[1]) possible.

References