AC Python 40 ms solution, O(n) time O(n) space using counting sort

  • 4
    def hIndex(self, citations):
        n = len(citations)
        papers = [0] * (n + 1)  # papers[i] is the number of papers with i citations.
        for c in citations:
            papers[min(n, c)] += 1  # All papers with citations larger than n is count as n.
        i = n
        s = papers[n]  # sum of papers with citations >= i
        while i > s:
            i -= 1
            s += papers[i]
        return i
    # 81 / 81 test cases passed.
    # Status: Accepted
    # Runtime: 40 ms
    # 97.08%

    The question is quite simple if the citations are sorted. Which means we need some kind of "sorting". The observation h index is limited by both citation and paper count gives us the idea of counting/bucket sort. We can consider any paper with citations larger than n as citation == n. This way we can sort the citations in O(n) time with O(n) space. The rest is trivial.

  • 0

    Nice solution. Thanks!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.