Problem URL: H-index

We will use count sort to sort the elements in linear time and then search for the highest value, where numbers of elements after that index is greater than or equal to that value.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        count = [0] * (max(citations)+1)
        for c in citations:
            count[c] += 1
        curSum, h = 0, 0
        for i in range(len(count)-1, -1, -1):
            curSum += count[i]
            h = max(h, min(curSum, i))
        return h

Time Complexity: O(n)
Space Complexity: O(1)