def hIndex(self, citations): n = len(citations) papers =  * (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.