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

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

Oneliner

If we do not use binary search, we can solve problem in one line, using linear search. We need to add [0] in the end to handle some border cases.

class Solution:
    def hIndex(self, c):
        return ([i+j>=len(c) for i,j in enumerate(c)][::-1]+[0]).index(0)

See also my solution of 254 problem H-Index:

If you like the solution, you can upvote it on leetcode discussion section: Problem 0275