Tuesday, December 22, 2015

Leetcode: Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.
Naive Solution 1: 
The first method is the most straight-forward. Use an array to store the numbers. So the update takes O(1) time. sumRange() takes O(n) time. 

Naive Solution 2:
Similar to the Range Sum Query - Immutable, we calculate the prefix of the elements in the array. Therefore, for the update(), it takes O(n) time to update the elements after the updated element. But the sumRange() take O(1) time. 

Better Solution:
Since the problem assumes that the two functions are called evenly, there exists a better method using Segment Tree in O(logn) time. 

Code (Java):
public class NumArray {
    class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left, right;
        
        // Constructor
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            sum = 0;
        }
        
        public SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
        
    }
    
    private SegmentTreeNode root;
    
    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        root = buildSegmentTree(nums, 0, nums.length - 1);
    }

    void update(int i, int val) {
        updateHelper(root, i, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int i, int val) {
        if (root == null) {
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        if (i <= mid) {
            updateHelper(root.left, i, val);
        } else {
            updateHelper(root.right, i, val);
        }
        
        if (root.start == root.end && root.start == i) {
            root.sum = val;
            return;
        }
        
        root.sum = root.left.sum + root.right.sum;

    }

    public int sumRange(int i, int j) {
        return sumRangeHelper(root, i, j);
    }
    
    private int sumRangeHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || end < root.start || start > root.end || 
            start > end) {
            return 0;
        }
        
        if (start <= root.start && end >= root.end) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        return sumRangeHelper(root.left, start, Math.min(end, mid)) + 
               sumRangeHelper(root.right, Math.max(mid + 1, start), end);
    }
    
    private SegmentTreeNode buildSegmentTree(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0 || start > end) {
            return null;
        }
        
        // Start == end
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
        }
        
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        int mid = start + (end - start) / 2;
        root.left = buildSegmentTree(nums, start, mid);
        root.right = buildSegmentTree(nums, mid + 1, end);
        
        root.sum = root.left.sum + root.right.sum;
        
        return root;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

Summary:
The take-away message for this problem is there is no such a BEST solution ever. You need to communicate with the interviewer to ask the use cases and choose the best solution. 

Update on 5/16/19:
class NumArray {
    SegmentTree segmentTree;

    public NumArray(int[] nums) {
        segmentTree = new SegmentTree(nums);
    }
    
    public void update(int i, int val) {
        segmentTree.update(i, val);
    }
    
    public int sumRange(int i, int j) {
        return segmentTree.search(i, j);
    }
}

class SegmentTree {
    public SegmentTreeNode root;
    public SegmentTree(int[] nums) {
        root = build(nums);
    }
    
    public int search(int start, int end) {
        return searchHelper(root, start, end);
    }
    
    private int searchHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || start > end) {
            return 0;
        }
        
        if (root.start == start && root.end == end) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        int leftSum = searchHelper(root.left, Math.max(root.start, start), Math.min(mid, end));
        int rightSum = searchHelper(root.right, Math.max(start, mid + 1), Math.min(root.end, end));
        
        return leftSum + rightSum;
    }
    
    public void update(int index, int val) {
        updateHelper(root, index, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int index, int val) {
        if (root == null) {
            return;
        }
        
        if (root.start == root.end && index == root.start) {
            root.sum = val;
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        if (index <= mid) {
            updateHelper(root.left, index, val);
        } else {
            updateHelper(root.right, index, val);
        }
        
        root.sum = root.left.sum + root.right.sum;
    } 
    
    private SegmentTreeNode build(int[] nums) {
        return buildHelper(0, nums.length - 1, nums);
    }
    
    private SegmentTreeNode buildHelper(int start, int end, int[] nums) {
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
        }
        
        int mid = start + (end - start) / 2;
        SegmentTreeNode leftChild = buildHelper(start, mid, nums);
        SegmentTreeNode rightChild = buildHelper(mid + 1, end, nums);
        
        SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.sum + rightChild.sum);
        root.left = leftChild;
        root.right = rightChild;
        
        return root;
    }
    
}

class SegmentTreeNode {
    int sum;
    int start, end;
    SegmentTreeNode left, right;
    
    public SegmentTreeNode(int start, int end, int sum) {
        this.sum = sum;
        this.start = start;
        this.end = end;
        left = right = null;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

Leetcode: Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Understand the problem:
Construct a 2D array sums[row+1][col+1]
(notice: we add additional blank row sums[0][col+1]={0} and blank column sums[row+1][0]={0} to remove the edge case checking), so, we can have the following definition
sums[i+1][j+1] represents the sum of area from matrix[0][0] to matrix[i][j]
To calculate sums, the ideas as below
+-----+-+-------+     +--------+-----+     +-----+---------+     +-----+--------+
|     | |       |     |        |     |     |     |         |     |     |        |
|     | |       |     |        |     |     |     |         |     |     |        |
+-----+-+       |     +--------+     |     |     |         |     +-----+        |
|     | |       |  =  |              |  +  |     |         |  -  |              |
+-----+-+       |     |              |     +-----+         |     |              |
|               |     |              |     |               |     |              |
|               |     |              |     |               |     |              |
+---------------+     +--------------+     +---------------+     +--------------+

   sums[i][j]      =    sums[i-1][j]    +     sums[i][j-1]    -   sums[i-1][j-1]   +  

                        matrix[i-1][j-1]
So, we use the same idea to find the specific area's sum.
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+
|               |   |         |    |   |   |           |   |         |    |   |   |          |
|   (r1,c1)     |   |         |    |   |   |           |   |         |    |   |   |          |
|   +------+    |   |         |    |   |   |           |   +---------+    |   +---+          |
|   |      |    | = |         |    | - |   |           | - |      (r1,c2) | + |   (r1,c1)    |
|   |      |    |   |         |    |   |   |           |   |              |   |              |
|   +------+    |   +---------+    |   +---+           |   |              |   |              |
|        (r2,c2)|   |       (r2,c2)|   |   (r2,c1)     |   |              |   |              |
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+


Code (Java):
public class NumMatrix {
    private int[][] matrix;
    private int[][] sum;
    
    public NumMatrix(int[][] matrix) {
        this.matrix = matrix;
        
        if (matrix == null || matrix.length == 0) {
            return;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        sum = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - 
                            sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - 
               sum[row1][col2 + 1] + sum[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);


Leetcode: Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.
Understand the problem:
For the naive solution, each time we call the sumRange(lo, hi), we sum up the numbers and return the result. So the time complexity would be O(n). 

Note that there are many calls to sumRange function, so we can calculate the prefix sum in the constructor. Then each time we call the sumRange(lo, hi), we just need to calculate the prefix[hi] - prefix[lo - 1], in O(1) time. 


Code (Java):
public class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        
        // Calculate the prefix sum
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        if (i < 0 || i >= nums.length || 
            j < 0 || j >= nums.length || 
            i > j) {
            return 0;
        }
        
        if (i == 0) {
            return nums[j];
        } else {
            return nums[j] - nums[i - 1];
        }
    }
}

Leetcode: Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Understand the problem:
A sequence DP problem. 
 -- dp[n + 1], where dp[i] means the length of the LIS, including the ith character. 
 -- Initial state: dp[0] = 0, dp[i] = 1, i >= 1
 -- Transit function: for j from [0, i), if (nums[i - 1] > nums[j - 1]), dp[i] = Math.max(dp[i], dp[j] + 1);
-- Final state: the max in dp[i]. 

Code (Java):
public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.length + 1];
        for (int i = 1; i < nums.length + 1; i++) {
            dp[i] = 1;
        }
        
        int maxLen = 1;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i - 1] > nums[j - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

Follow-up: Could you solve it in O(nlogn) time?
https://leetcode.com/discuss/67609/short-java-solution-using-dp-o-n-log-n

Monday, December 21, 2015

Leetcode: Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.
For example:
Secret number:  "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 01 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".
Please note that both secret number and friend's guess may contain duplicate digits, for example:
Secret number:  "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases.
Understand the problem:
The idea is first go through the input and get the number of bulls. Meanwhile, maintain a map and update the secret number in the map. 

The second pass is to calculate the the number of cows. The method is for each character in the guess, if it is not the bull, we check if this char is in the map. If yes, we found one cow. Remember we need to remove the visited chars in the map because of the duplicated number may occur in the secret. 

Code (Java):
public class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || secret.length() == 0 || 
            guess == null || guess.length() == 0) {
            return "0A0B";
        }
        
        int numBulls = 0;
        int numCows = 0;
        
        Map<Character, Integer> map = new HashMap<>();
        
        // Step 1: calculate the number of bulls and update the map
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            
            if (s == g) {
                numBulls++;
            } else {
                // Update the map
                if (map.containsKey(s)) {
                    int freq = map.get(s);
                    freq++;
                    map.put(s, freq);
                } else {
                    map.put(s, 1);
                }
            }
        }
        
        // Step 2: calculate the number of cows
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            
            if (s != g) {
                if (map.containsKey(g)) {
                    numCows++;
                    // update the map
                    if (map.get(g) == 1) {
                        map.remove(g);
                    } else {
                        int freq = map.get(g);
                        freq--;
                        map.put(g, freq);
                    }
                }
            }
        }
        
        return numBulls + "A" + numCows + "B";
    }
}

Analysis:
Time: O(n)
Space O(n)

A better solution:
Since the digits are only from 0 to 9, we don't need a map to store the digits, but just use two arrays, and count the freq for each digit. 

Code (Java):
public class Solution {
    public String getHint(String secret, String guess) {
        if (secret == null || secret.length() == 0 || 
            guess == null || guess.length() == 0) {
                return "0A0B";
        }
        
        int numBulls = 0;
        int numCows = 0;
        int[] s = new int[10];
        int[] g = new int[10];
        
        // Step 1: count the number of bulls
        for (int i = 0; i < secret.length(); i++) {
            char charS = secret.charAt(i);
            char charG = guess.charAt(i);
            
            if (charS == charG) {
                numBulls++;
            } else {
                s[charS - '0']++;
                g[charG - '0']++;
            }
        }
        
        // Step 2: count the number of cows
        for (int i = 0; i < 10; i++) {
            numCows += Math.min(s[i], g[i]);
        }
        
        return numBulls + "A" + numCows + "B";
    }
}

Sunday, December 20, 2015

Leetcode: Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).
For example,
   1
    \
     3
    / \
   2   4
        \
         5
Longest consecutive sequence path is 3-4-5, so return 3.
   2
    \
     3
    / 
   2    
  / 
 1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

Solution using global variables:
Maintain two variables, one is the local length of the consecutive path, the other is the global variable of the longest local length. 

We do a DFS, i.e, pre-order traversal of a binary tree. For each node of which value equals to the target value (parent value plus one), increase the local length. Otherwise, set the local length to 1. Meanwhile, update the global length. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxLen = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        longestConsecutiveHelper(root, 1, root.val + 1);
        return maxLen;
    }
    
    private void longestConsecutiveHelper(TreeNode root, int length, int target) {
        if (root == null) {
            return;
        }
        
        int curLen = 0;
        if (root.val == target) {
            curLen = length + 1;
        } else {
            curLen = 1;
        }
        
        maxLen = Math.max(maxLen, curLen);
        longestConsecutiveHelper(root.left, curLen, root.val + 1);
        longestConsecutiveHelper(root.right, curLen, root.val + 1);
        
    }
}

Solution without using global variables:
We can use the return value to pass the global maximal length. Then everything else is the same as the previous solution. 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return longestConsecutiveHelper(root, 0, root.val + 1);
    }
    
    private int longestConsecutiveHelper(TreeNode root, int curLen, int target) {
        if (root == null) {
            return curLen;
        }
        
        if (root.val == target) {
            curLen += 1;
        } else {
            curLen = 1;
        }
        
        int left = longestConsecutiveHelper(root.left, curLen, root.val + 1);
        int right = longestConsecutiveHelper(root.right, curLen, root.val + 1);
        
        return Math.max(curLen, Math.max(left, right));
    }
}

Saturday, December 19, 2015

Leetcode: Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: 
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.
For example:
add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Understand the problem:
Use two heaps. The maxHeap stores the number which is less than the current number. The minHeap stores the number which is greter than the current number. 
We also need to keep the two heaps balanced in size. 

For the method findMedian(), we need to check if the two heaps have the same size. If yes, there must be even number of elements so far, so the median is the average of the top of the minHeap and the maxHeap. If not, i.e. odd number of elements so far, the median is the top of the heap which one more element. 

Code (Java):
import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> leftPQ = 
        new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> rightPQ = new PriorityQueue<>();
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        if (leftPQ.isEmpty() || num <= leftPQ.peek()) {
            leftPQ.offer(num);
        } else {
            rightPQ.offer(num);
        }
        
        // Rebalance the pqs
        if (leftPQ.size() - rightPQ.size() > 1) {
            rightPQ.offer(leftPQ.poll());
        } else if (rightPQ.size() - leftPQ.size() > 1) {
            leftPQ.offer(rightPQ.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (leftPQ.isEmpty() && rightPQ.isEmpty()) {
            throw new NoSuchElementException(); // if the queue is empty
        }
        
        if(leftPQ.isEmpty()) {
            return (double) rightPQ.peek();
        } else if (rightPQ.isEmpty()) {
            return (double) leftPQ.peek();
        } else if (leftPQ.size() > rightPQ.size()) {
            return (double) leftPQ.peek();
        } else if (rightPQ.size() > leftPQ.size()) {
            return (double) rightPQ.peek();
        } else {
            return (double) (leftPQ.peek() + rightPQ.peek()) / 2;
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();


Update 3/19/19:
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();

        int[] ans = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (maxPQ.isEmpty() || num <= maxPQ.peek()) {
                maxPQ.offer(num);
            } else {
                minPQ.offer(num);
            }

            rebalacne(maxPQ, minPQ);

            ans[i] = maxPQ.peek();
        }
        
        return ans;
    }

    private void rebalacne(PriorityQueue<Integer> maxPQ, PriorityQueue<Integer> minPQ) {        
        if (maxPQ.size() - minPQ.size() > 1) {
            minPQ.offer(maxPQ.poll());
        } else if (minPQ.size() - maxPQ.size() > 0) {
            maxPQ.offer(minPQ.poll());
        }
    }
}