**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**