H-Index

LeetCode 274 | Difficulty: Medium

Medium

Problem Description

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i^th paper, return the researcher's h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

Constraints:

- `n == citations.length`

- `1 <= n <= 5000`

- `0 <= citations[i] <= 1000`

Topics: Array, Sorting, Counting Sort

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 147 ms)

Metric	Value
Runtime	147 ms
Memory	35.9 MB
Date	2022-01-17

Solution

public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
    int[] cited = new int[n+1];
    foreach (var c in citations)
    {
        if(c>n)
        {
            cited[n]++;
        }
        else
        {
            cited[c]++;
        }
    }
    
    int total = 0;
    for (int i = n; i >= 0; i--)
    {
        total += cited[i];
        if(total >= i)
        {
            return i;
        }
    }
    return 0;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: An easy approach is to sort the array first.

Hint 2: What are the possible values of h-index?

Hint 3: A faster approach is to use extra space.