Leetcode 275 Solution

Leetcode Question Link

https://leetcode.com/problems/h-index-ii

Thinking Process

Let’s first figure out a linear solution, which is straightforward. We’ll just go through the citations array, and try each element i. if citations[i] >= n - i, we know that this scientist’s index is at least n - i. So let’s just do that for each element, and the first one that meets the condition citations[i] >= n - i is our target, and the result will be n - i.

Now, let’s try to make it O(lg N). Remember our binary search principle here. In this question, the function citations[i] >= n - i has already helped us map the original array to an 0-1 array, and our goal is to find the index of the first 1. We’ll just need to put it into our binary search template binary_search_template, and we get the result.

Time & Space Complexity

Assuming N is the size of the array:

• Time complexity: O(lg N)
• Space complexity: O(1)

Solution

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int l = 0;
        int r = citations.size() - 1;

        while (l <= r)
        {
            int m = (l + r) / 2;

            if (citations[m] >= citations.size() - m)
                r = m - 1;
            else
                l = m + 1;
        }

        return citations.size() - l;
    }
};