Leetcode 275 : H-Index II

https://leetcode.com/discuss/56122/standard-binary-search

Code 1: 

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        for i in xrange(len(citations)):
            if citations[i] >= len(citations) - i:
                return len(citations) - i
        return 0

Code 2:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        left, right = 0, len(citations)-1
        while left < right:
            mid = (left + right) / 2
            if citations[mid] < (len(citations) - mid):
                left = mid +1
            else:
                right = mid - 1
        print left
        if citations[left] >= len(citations) - left:
            return len(citations) - left
        elif left+1 <= len(citations)-1 and citations[left+1] >= len(citations) - left -1: 
            return len(citations) - left -1
        else:
            return 0

Code 3:

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations is None or len(citations) == 0:
            return 0
        left, right = 0, len(citations)-1
        while left <= right:
            mid = (left + right) / 2
            if citations[mid] < (len(citations) - mid):
                left = mid +1
            elif citations[mid] > (len(citations) - mid):
                right = mid - 1
            else:
                return len(citations) - mid
                
        return len(citations) - right- 1

 

 

Idea:

Code 1 takes O(N) time to traverse every citation backwards. But actually, since citations are already sorted, you can use binary search to achieve O(logN) time complexity. We will take code 3 for example. (Code 2 is ugly implemented by my intermediate thoughts, so skip it.) We create `left` and `right` pointers. We use `mid` to binary search the correct point `i`, at which we can return len(citations) – i as h-index. `i` should have the following properties:

1. citations[j] < len(citations)-j for j < i
2. citations[k] >= len(citations)-k for k>=i

We have two condition branches in line 13 and line 15. In this way, we always make sure that:

a. `citations[right+1] > len(citations) – right -1` holds.

b. `citations[left-1] < len(citations) – left +1` holds

The last execution of while loop is when left == right == mid: you check `citations[mid] ? len(citations) – mid` the last time:

1. If line 13 holds, you know that current `right` has: `citations[right] < len(citations) – right`. You set `left = mid + 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. From property a, we know that: `citations[right+1] > len(citations) – right -1`. Therefore we return `len(citations)-right-1` as h-index.
2. If line 15 holds,  you know `right` before set to `mid-1` has: `citations[right] > len(citations) – right`. Then you set `right = mid – 1`. Then the while loop terminates because `left<=right` doesn’t hold anymore. Now, `right = mid – 1 = left – 1`. From property b, we know: `citations[right] < len(citations) – right`. So we still return `len(citations)-right-1` as h-index.

This works even in the corner case in which `citations=[0,0,…,0]` because right will be initialized as `len(citations)-1` and will not get changed in the while loop. At the last line, `len(citations)-right -1 =0`, which is still the correct h-index for this case.

 

Reference:

https://leetcode.com/discuss/56122/standard-binary-search