LeetCode June Challenge - Day 18

Problem: LeetCode June Challenge - Day 18

Ideas:

  1. A scientist has h-index k iff he/she has k papers with k citations. Since the array is sorted, if the last k citations don’t meet this requirement, none will. Therefore, a scientist has h-index k iff the k-th element from the end is equal or greater than k.
  2. A scientist with h-index k also has h-index k-1, k-2, … , 0, so we can use binary search.

Solution:

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if(n == 0)
            return 0;

        int lo = 0, hi = n-1;
        while(lo <= hi){
            int m = (hi+lo)/2;
            if(citations[m] >= n-m) hi = m-1;
            else lo = m+1;
        }
        return n-lo;
    }
};