H-Index II Problem

Question

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:

• This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
• Could you solve it in logarithmic time complexity?

Answer 1

Binary search

In this problem data is already sorted for you, so we should take advantage of it. What you think what you need to search in sorted data? The answer is binary search. Of course you can not apply it like this, you need to adapt it to our problem. Let us start with example [1,3,3,3,4,4,7] and then consider general case.

......X

......X

......X

....XXX

.XXXXXX

.XXXXXX

XXXXXXX

What is the answer fo this data? It is 3, because there is 3 publications with at least 3 citations:

......X

......X

......X

....XXX

.XXXOOO

.XXXOOO

XXXXOOO

I denoted found elements as O. We can see, that what we actually need to find, is the size of biggest square which is inside our sorted data. Mathematically speaking, we look for smallest index i, such that i + citations[i] >= n and then we return n-i. In our example n=7, i = 4 and answer is 7 - 4 = 3. How we find this smallest index i? Using binary search of course, because sequence i + citations[i] is non-decreasing.

We can not use bisect library here, because for this we need to calculate i + citations[i] for every i, which can be done only in O(n), so we need to apply vanila binary search by hands.

Complexity:

 time complexity is O(log n) and additional space complexity is O(1).

class Solution:     def hIndex(self, citations):         if not citations: return 0         n = len(citations)         beg, end = 0, n - 1         while beg <= end:             mid = (beg + end)//2             if mid + citations[mid] >= n:                 end = mid - 1             else:                 beg = mid + 1                         return n - beg

eg :  ans = Solution()

ans.hIndex([0,1,3,5,6])

Output-

3