Easy and concise standard binary search solution in Java with detailed explanation


  • 1
    A
    public int hIndex(int[] citations) {
        int n = citations.length;
        
        int l = 0;
        int r = citations.length - 1;
        
        while (l <= r) {
            int m = (l + r) / 2;
            if (citations[m] >= n - m) { // It checks if it's a valid H-Index
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        
        return n - l;
    }
    

    The basic idea is that the sorted citations can be treated as two part: the left half of array are not H-index and the right half of array are H-index, our goal is to get the leftmost index of the right half so that the right half part will have maximum number of elements (what question asked). In this case, we can use standard binary search to search for this leftmost element. If m is in the right half, we make r = m - 1 , else l = m + 1.

    Note: I use while (l <= r) for two reasons:

    1. If all the elements in array are 0s, pointer l will end up with index n (length of array), then return n - l will return 0.
    2. Since r = m - 1 will cause pointer r end up with being the rightmost element in left half, l <= r can make sure pointer l stops at index to the right of r which is the leftmost element of right half.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.