Find H-Index

This is a very important interview + concept-based sorting problem.

Problem Summary

You are given an array citations[], where:

• citations[i] = number of citations of paper i

You must find the H-index, defined as:

Maximum value H such that at least H papers have ≥ H citations

Key Insight

We want to find a point where:

count of papers ≥ H  >= H

Optimal Approach (Sorting)

Step 1: Sort in descending order

Now:

• index = number of papers with higher citations

Step 2: Check condition

If at position i:

citations[i] >= i + 1

Then update H = i + 1

Example

Input

[3, 0, 5, 3, 0]

Sorted

[5, 3, 3, 0, 0]

Check

i	citations[i]	i+1	Valid
0	5	1	YES
1	3	2	YES
2	3	3	YES
3	0	4	NO

Answer = 3

Java Solution

import java.util.*;

class Solution {
    public int hIndex(int[] citations) {

        Arrays.sort(citations);

        int n = citations.length;
        int h = 0;

        // traverse from end (highest citations first)
        for (int i = n - 1; i >= 0; i--) {

            int papers = n - i; // number of papers considered

            if (citations[i] >= papers) {
                h = papers;
            } else {
                break;
            }
        }

        return h;
    }
}

Complexity

• Time Complexity: O(n log n) (sorting)

• Space Complexity: O(1) (ignoring sort space)

Key Takeaways

• H-index is about balance between quantity and citations

• Sorting simplifies the condition

We check:

“How many papers have at least X citations?”

Pattern Recognition

If you see:

• ranking / threshold problems

• “at least k elements satisfy condition”

• maximize such k

Think:

Sorting + greedy threshold check