You are given an array where each element represents the number of citations a researcher has received for each of their papers. The goal is to compute the H-Index.

The H-Index is defined as:

A researcher has an H-index of h if h of their papers have at least h citations each, and the remaining papers have no more than h citations.

Examples:

Input:  [3,0,6,1,5]
Output: 3

Because:

• 3 papers have at least 3 citations
• The remaining papers have ≤ 3 citations

---

Problem Understanding

Given:

• An integer array citations
• Length represents total papers
• Values represent citation counts

Goal:

• Return the maximum possible h that satisfies the definition

Constraints:

• Array size up to 5000
• Citation counts can be large
• We must find an efficient method

---

Logic Explained in Simple English

To understand the H-index intuitively:

1. If a person has many papers, but none cited much → low H-index
2. If a person has few papers, but highly cited → H-index limited by paper count
3. The H-index increases only when:
   • there are enough papers with citation counts above a threshold

A simple way to detect this:

Strategy

1. Sort the citations in descending order
2. Walk through the sorted list
3. Count how many papers have citations ≥ their index position + 1
4. The highest such count is the H-index

Example:
Sorted: [6,5,3,1,0]

Check:

• Paper 1 has 6 citations → ≥ 1 ✅
• Paper 2 has 5 citations → ≥ 2 ✅
• Paper 3 has 3 citations → ≥ 3 ✅
• Paper 4 has 1 citation → ≥ 4 ❌ stop

So H-index = 3

Why this works:

• Sorting puts highly cited papers first
• We test how many can satisfy required threshold

---

Step-by-Step Approach

Method (Sorting Approach)

1. Sort citations in descending order
2. Initialize h = 0
3. Loop over sorted values:
   • If citations[i] ≥ i + 1, increment h
   • Else stop
4. Return h

This is simple and works efficiently.

---

Java Implementation

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;
        
        for (int i = 0; i < n; i++) {
            int papersWithAtLeastCitations = n - i;
            if (citations[i] >= papersWithAtLeastCitations) {
                h = papersWithAtLeastCitations;
                break;
            }
        }
        
        return h;
    }
}

Alternative descending iteration version:

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0;
        int n = citations.length;

        for (int i = 0; i < n; i++) {
            int candidate = n - i;
            if (citations[i] >= candidate) {
                h = candidate;
                break;
            }
        }
        
        return h;
    }
}

---

Dry Run Example

Input:

[3,0,6,1,5]

Step 1: Sort ascending

[0,1,3,5,6]

Step 2: Iterate

i = 0
candidate = 5
citations[0] = 0
0 ≥ 5? No

i = 1
candidate = 4
citations[1] = 1
1 ≥ 4? No

i = 2
candidate = 3
citations[2] = 3
3 ≥ 3? Yes → h = 3 → stop

Final Output:

3

---

Time and Space Complexity

Time Complexity

O(n log n)
(due to sorting)

Space Complexity

O(1)
(in-place sorting allowed)

---

Common Mistakes and How to Avoid Them

Mistake 1: Counting citations instead of papers

The definition requires:

h papers with at least h citations each

Mistake 2: Trying to match exact values

H-index is a maximum threshold, not exact equality.

Mistake 3: Forgetting sort direction

Descending or ascending handled properly matters.

Mistake 4: Assuming citations must reduce monotonically

Real data can be unordered.

Mistake 5: Confusing with cumulative sums

Summation has no role here — only comparison counts.