How do you solve H-Index on LeetCode?

H-Index (LeetCode #274) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting helps in efficiently determining the h-index by leveraging the order of citations.

What is the brute force solution for H-Index?

The brute force approach for H-Index is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each possible value of h from 0 to the maximum number of papers. For each h, it counts how many papers have at least h citations. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve H-Index?

H-Index uses the following concepts: Array, Sorting, Counting Sort. The recommended patterns to study are: Sorting, Array.

What are the interview tips for H-Index?

Always clarify the problem statement and constraints before jumping into coding. Think about edge cases and test your solution against them. Explain your thought process clearly while coding; it shows your understanding.

What are common mistakes when solving H-Index?

Not considering edge cases, such as when all citations are zero. Confusing the definition of h-index with other metrics like g-index.

#274

H-Index

Medium

ArraySortingCounting SortSortingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

By sorting the citations array, we can quickly determine the h-index by leveraging the sorted order. The h-index is simply the largest h such that the h-th paper has at least h citations.

⚙️

Algorithm

4 steps

1Step 1: Sort the citations array in non-decreasing order.
2Step 2: Iterate through the sorted array, checking if the current index (i) plus one (to account for 0-based index) is less than or equal to the citation at that index.
3Step 3: If it is, update the h-index to i + 1.
4Step 4: Continue until you reach the end of the array.

solution.py9 lines

1# Full working Python code
2
3def hIndex(citations):
4    citations.sort()
5    n = len(citations)
6    for i in range(n):
7        if citations[i] >= i + 1:
8            h = i + 1
9    return h

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, while the space complexity is O(1) since we are sorting in place.

1Sorting helps in efficiently determining the h-index by leveraging the order of citations.
2The h-index can be thought of as a threshold that balances the number of papers and their citation counts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.