Showing posts with label binary search. Show all posts
Showing posts with label binary search. Show all posts

Friday, December 18, 2015

Count of Smaller Numbers After Self [LeetCode]

Problem Description
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].
Solution
In this post, I'm going to write a little bit about Binary Indexed Tree and its application to solve the above problem. The problem itself is not really hard. We can solve it using many ways, including Binary Search Tree, Segment Tree, Sorting, or language specific way such as using lower_bound in C++, TreeSet (or SortedSet) in Java with method lower  (see some at the end) .
Once we know how to use Binary Indexed Tree or shortly BIT, we can solve many other problems, especially in programming contests since BIT is very easy to implement.

I suggest that you spend some time to read this article from Topcoder: Binary Indexed Tree.
Basically, in this problem, we use BIT to count the number of integers that are less than a specific number.
Suppose that a number N = A1B > 0 in binary representation, where B contains all 0 . The array tree is a BIT where tree[N] count the number of integers that are from A0B and A1B - 1 .
So if we call f[N] is the number of integers that are less than N, how we calculate its value?
Yes, you are correct, f[N] = tree[N] + f[A0B] (where A0B is in binary representation).
We also know that A0B = N & (N-1) using bit manipulation. (NOTE: on the Topcoder, they use A0B= N - (N & -N) .  
Having this in mind, to solve the problem we run from the back of the array, try each element. At the position i , we can simply calculate f[nums[i]] and put it into the result. However, we need to update the BIT here, because we have found another integer. So the natural question is which element we need to update in the BIT? Obviously, we need to update tree[N+1] by increasing its value by 1. But we do not stop there. Let N+1 = C1D where D has all 0 . As you can see, let  g[N+1] = C1D + 1D , we need to update g[N+1] also. And in turn, we need to update g[g[N+1]],so on...

Let's see the following Java code for implementation.
public class Solution {
    
    /*
    In this solution, we use a binary indexed tree (BIT)
    Our assumption is that all elements in nums are positive
    */
    
    static int MAX = 11000; //we set max value that can be store in the tree
    int[] tree = new int[MAX];
    
    public List<Integer> countSmaller(int[] nums) {
        Integer[] result = new Integer[nums.length];
        
        //make all elements in the array posive while maintaining their order
        makePositive(nums);
    
        for(int i=nums.length-1; i>=0; i--){
            result[i] = get(nums[i]);
            add(nums[i]+1, 1);
        }
        return Arrays.asList(result);
    }
    
    public void makePositive(int[] nums){
        int min = MAX;
        for(int i=0; i<nums.length; i++)    
            min = Math.min(min, nums[i]);
        if(min < 0){
            min = -min+1;
            for(int i=0; i<nums.length; i++)
                nums[i] += min;
        }
    }
    
    public void add(int idx, int val){
        while(idx<MAX){
            tree[idx] += val;
            idx += (idx & (-idx));
        }
    }
    
    public int get(int idx){
        int result = 0;
        while(idx>0){
            result += tree[idx];
            idx &= (idx-1);
        }
        return result;
    }
}
Appendix A: Binary search Tree solution (Java) - Credited to  yavinci
public class Solution {
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
}
Appendix B: Segment Tree Solution (Javascript) - Credited to opmiss.
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
    if (nums.length<1) return []; 
    var SegmentTreeNode = function(s, e){
        this.start = s;
        this.end = e; 
        this.left = null; 
        this.right = null; 
        this.count = 0; 
    }; 
    var max = nums[0]; 
    var min = nums[0]; 
    nums.forEach(function(num){
        max = (max<num)?num:max; 
        min = (min>num)?num:min; 
    }); 
    var root = new SegmentTreeNode(min, max);
    var insert = function(node, num){
        ++node.count; 
        if (node.start===node.end){
            return 0; 
        }
        if (node.left===null){
            var mid = (node.start+node.end)>>1; 
            node.left = new SegmentTreeNode(node.start, mid); 
            node.right = new SegmentTreeNode(mid+1, node.end); 
        }
        if (num>node.left.end){
            var res=node.left.count+insert(node.right, num);
            return res; 
        }
        return insert(node.left, num); 
    }; 

    var res = []; 
    while (nums.length>0){
       res.unshift(insert(root, nums.pop()));  
    }
    return res; 
};
Appendix C: Merge sort (Java) - Credited to  lzyfriday.
int[] count;
public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();     

    count = new int[nums.length];
    int[] indexes = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
        indexes[i] = i;
    }
    mergesort(nums, indexes, 0, nums.length - 1);
    for(int i = 0; i < count.length; i++){
        res.add(count[i]);
    }
    return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
    if(end <= start){
        return;
    }
    int mid = (start + end) / 2;
    mergesort(nums, indexes, start, mid);
    mergesort(nums, indexes, mid + 1, end);

    merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
    int mid = (start + end) / 2;
    int left_index = start;
    int right_index = mid+1;
    int rightcount = 0;     
    int[] new_indexes = new int[end - start + 1];

    int sort_index = 0;
    while(left_index <= mid && right_index <= end){
        if(nums[indexes[right_index]] < nums[indexes[left_index]]){
            new_indexes[sort_index] = indexes[right_index];
            rightcount++;
            right_index++;
        }else{
            new_indexes[sort_index] = indexes[left_index];
            count[indexes[left_index]] += rightcount;
            left_index++;
        }
        sort_index++;
    }
    while(left_index <= mid){
        new_indexes[sort_index] = indexes[left_index];
        count[indexes[left_index]] += rightcount;
        left_index++;
        sort_index++;
    }
    while(right_index <= end){
        new_indexes[sort_index++] = indexes[right_index++];
    }
    for(int i = start; i <= end; i++){
        indexes[i] = new_indexes[i - start];
    }
}
Appendix D: Merge sort (Python) - Credited to StefanPochmann
def countSmaller(self, nums):
    def sort(enum):
        half = len(enum) / 2
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                if not right or left and left[-1][1] > right[-1][1]:
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        return enum
    smaller = [0] * len(nums)
    sort(list(enumerate(nums)))
    return smaller

Monday, September 7, 2015

First Bad Version [LeetCode]

Problem Description
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Solution
This is a typical example of type of binary search that does not return immediately after finding the satisfied element.
Suppose we have 2 pointers start and end. We take middle = (start + end) / 2. Now we check if middle is a bad version. If it is yes, we do not stop here, but we will search on the left, in order to find out that whether there is some smaller bad version. By going to the left, we set end = middle - 1. So if we find nothing on the left, we return end + 1, because it is the last time we saw a bad version. If middle is not a bad version, we simply go to the right by setting start = middle + 1.

One thing to note is that in some programming language, to avoid overflow, we use (end-start)/2 + start instead of (start + end)/2
I. Python Code
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, middle, end = 1, 1, n
        while start <= end:
            middle = (start + end) >> 1
            if isBadVersion(middle): end = middle - 1
            else: start = middle + 1
        return end + 1
II. Java Code
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        int middle;
        while(start <= end){
            middle = ((end - start)>>1) + start;
            if (isBadVersion(middle)) end = middle - 1;
            else start = middle + 1;
        }
        return end + 1;
    }
}
III. C++ Code
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        int middle;
        while(start <= end){
            middle = ((end-start)>> 1) + start;
            if(isBadVersion(middle)) end = middle - 1;
            else start = middle + 1;
        }
        return end + 1;
    }
};
IV. Javascript Code
/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        var start = 1;
        var end = n;
        while(start <= end){
            var middle = ((end-start) >> 1) + start;
            if (isBadVersion(middle)) end = middle - 1;
            else start = middle + 1;
        }
        return end + 1;
    };
};

Sunday, September 6, 2015

H-Index II [LeetCode]

Problem Description
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Solution
In the previous version, we sorted citations in reverse order. In this version of problem, the citations array is in ascending order.
I. O(n) Solution
As we already know in the previous version of finding H-Index, we can solve the problem in linear time. Below is the 1-line Python solution:
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        return max(min(v, len(citations)-k) for k, v in enumerate(citations + [0]))
II. O(logn) Solution
Since we already knew about how to solve the problem in linear time, we try to find another solution. As usual, the idea is to find O(logn) solution by binary search.
Our normal logic when using binary search is that we have a start and end point. We will check the middle= (start + end) /2. (In some language, to avoid overflow we can use (end-start)/2 + start )
What we need to find out now is when we should stop the search, or going to left or right.


1. When we should stop?
Suppose that middle is not in final stage (where start > end) and we decide to stop. There are (n-middle) elements are at least citations[middle], and other (middle ) elements are at most citations[middle]. This suggests that if citations[middle] = (n-middle) = h (where n is the number of elements in citations),  then we have at least h elements are at least h, and other middle = n-h elements are at most h. So h is an H-index.
Is it h  the largest? Suppose there is another h" > h and h" is also an H-index. Consider the element at n-h". Since there are at least h" elements which are at least h", then citations[n-h"] >= h">h. However, we have n-h" < n-h, therefore citations[n-h"] < citations[n-h] = h, or we have h > h. This is contradictory. So h is the largest H-index. This means that we should stop the search here!

2. When we should go to the left and right
The analysis in (1) suggest that we should compare citations[middle] and (n-middle) in order to decide whether we should go to left or right in binary search.

a. If citations[middle] < n-middle: 
Is it possible to stop or go left in this case? Suppose it is. That means there is a number h >= n-middle, and h is an H-index. Then there are h elements which are at least h. Therefore:
citations[n-h] > h >= n-middle > citations[middle]
However,
h >= n-middle  => middle >= n-h
That means citations[n-h] <= citations[middle]. This is contradictory.
So we should go to the right in this case.

b. If citations[middle] > n-middle: 
This is not same as the case (a). Easily we can see that h = n-middle is an H-index. But there might be other elements on the left satisfy the H-index condition. So we simply go to the left to search more.
Note that the current position is end + 1 after we set the end pointer to middle-1. And also, while searching on the left, if we go to the left another time, then current h= n-middle is not the largest H-index. But if we never go to the left again, then the pointer end keeps unchanged, so we can simply return n-end-1 when the search is terminated.
We come to coding now.

I. Python Code
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations) 
        start, end = 0, n-1
        while start <= end:
            middle = (start + end) / 2
            if citations[middle] == n-middle: return citations[middle]
            elif citations[middle] < n - middle: start = middle + 1
            else: end = middle - 1
        return n-end-1
II. Java Code
public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int start = 0;
        int end = n-1;
        int middle;
        while (start <= end){
            middle = (end-start)/2 + start;
            if (citations[middle] == n-middle) return citations[middle];
            else if(citations[middle] < n-middle) start = middle + 1;
            else end = middle - 1;
        }
        return n - end - 1;
    }
}
III. C++ Code
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int start = 0;
        int end = n - 1;
        int middle = 0;
        while(start <= end){
            middle = (end-start)/2 + start;
            if (citations[middle] == n-middle) return citations[middle];
            else if(citations[middle] < n-middle) start = middle + 1;
            else end = middle - 1;
        }
        return n-end-1;
    }
};

Wednesday, August 5, 2015

Calculate x to the power of n

Problem Description
Implement pow(x, n) where x is a float and n is an integer.

Solutions
Analysis: This problem is pretty simple. We can calculate it in O(n) time. But we can also easily do it in O(log n ) time.

I. Recursive Solution - O(log n)
class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = self.myPow(x, n/2) if n>0 else self.myPow(1/x, -(n/2))
        return result * result * (x if n % 2 == 1 else 1)
II. Non-recursive Solution - O(log n) time - O(log n) space
This solution use one additional array, which is quite obvious.
class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = 1
        a = []
        t = n if n>0 else -n
        
        while t > 0:
            a.append(t % 2)
            t = t >> 1
        for i in range(1,len(a)+1):
            result = result * result * (1 if a[-i] == 0 else x)
        
        if n <0 : result = 1.0 / result
        return result
III. Non-recursive Solution - O(log n) time - O(1) space
This is an improvement on the solution numbered II.
class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        m = n
        if n < 0:
            m = -m
            x = 1/x
        
        result = 1
        while m > 0:
            
            if (m & 1) == 1:
                result *= x
            x *= x
            m >>=1
            
        return result  

Wednesday, June 24, 2015

LeetCode: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Solution: 
Below is a simple solution in Python:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:

    def insert(self, intervals, newInterval):
        l = []
        count = 0
        while(count < len(intervals)):
            if(newInterval.start <= intervals[count].end):
                if(newInterval.end >= intervals[count].start):
                    newInterval.start = min(intervals[count].start, newInterval.start)
                break
            l.append(intervals[count])
            count += 1
        l.append(newInterval)
        while(count < len(intervals)):
            if(newInterval.end < intervals[count].start):
                break
            l[-1].end = max(intervals[count].end, l[-1].end)
            count += 1
        while(count < len(intervals)):
            l.append(intervals[count])
            count += 1
        return l

And here is a faster solution using binary search:
class Solution:  
  
    def insert(self, intervals, newInterval):  
        if len(intervals) == 0:  
            return [newInterval]  
              
        v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)  
        v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)  
   
        if (v1 & 1):  
            newInterval.start = intervals[v1>>1].start   
        if (v2 & 1):  
            newInterval.end = intervals[(v2)>>1].end 
                  
        return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:] 
          
    def search(self, intervals, index, start=0, end=0, isStart=0):  
        while(start <= end):  
            middle = (end+start)>>1 
            if intervals[middle].start <= index and intervals[middle].end >= index:  
                return (middle << 1)+1 
            if intervals[middle].start > index:  
                end = middle - 1
            else:
                start = middle + 1       
        return start << 1

Third solution:
class Solution: 
  
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right

If you want to train the code reading skills, here is another approach in Java:
/**
 * Definition for an interval.
 **/
class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval){
        List<Interval> is = new ArrayList<Interval>();
        if(intervals == null || newInterval == null) return is;

        int status = 0;
        Interval open = null;
        for(Interval i: intervals){

            //if not found a interval containing the newInterval
            if(status==0){
                if(i.start > newInterval.end){
                    is.add(newInterval);
                    is.add(i);
                    status = 2;
                }else if(i.end < newInterval.start){
                    is.add(i);
                }else if(i.start<= newInterval.start && i.end < newInterval.end){
                    open = new Interval(i.start, newInterval.end);
                    status = 1;
                }else if(i.start > newInterval.start && i.end < newInterval.end){
                    status = 1;
                    open = new Interval(newInterval.start, newInterval.end);
                }else {
                    is.add(new Interval(Math.min(newInterval.start, i.start), i.end));
                    status = 2;
                }
            }else if(status == 1){
                if(i.start <= newInterval.end && i.end>= newInterval.end){
                    status = 2;
                    open.end = i.end;
                    is.add(open);
                }else if(i.start > newInterval.end){
                    status = 2;
                    open.end = newInterval.end;
                    is.add(open);
                    is.add(i);
                }                
            }else {   //status = 2
                is.add(i);
            }
        }

        if(status == 0) is.add(newInterval);
        if(status == 1){
            open.end = newInterval.end;
            is.add(open);
        }
        return is;
    }
}