# H-Index
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/h-index)
Canonical: https://scaleengineer.com/dsa/problems/h-index
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Nvidia](https://scaleengineer.com/companies/nvidia), [Zoox](https://scaleengineer.com/companies/zoox)
---
## Problem
Given an array of integers `citations` where `citations[i]` is the number of citations a researcher received for their `ith` paper, return _the researcher's h-index_.

According to the [definition of h-index on Wikipedia](https://en.wikipedia.org/wiki/H-index): 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`

# Approaches
## Brute Force Approach
Check each possible h-index value from 1 to n by counting papers with citations greater than or equal to the current h-index value.
**Time:** O(n²) where n is the length of citations array · **Space:** O(1) constant space
**Pros:** Simple to understand and implement; No additional space required; Works with unsorted input
**Cons:** Not efficient for large inputs; Performs unnecessary iterations
### Explanation
For each possible h-index value h from 1 to n:
1. Count the number of papers that have citations >= h
2. If the count is >= h, update the maximum h-index
3. Continue until we've checked all possible values

```java
public int hIndex(int[] citations) {
    int n = citations.length;
    int maxHIndex = 0;
    
    for (int h = 1; h <= n; h++) {
        int count = 0;
        for (int citation : citations) {
            if (citation >= h) {
                count++;
            }
        }
        if (count >= h) {
            maxHIndex = Math.max(maxHIndex, h);
        }
    }
    
    return maxHIndex;
}
```
### Algorithm
1. Initialize maxHIndex = 0
2. For h from 1 to n:
   - Count papers with citations >= h
   - If count >= h, update maxHIndex
3. Return maxHIndex

## Sorting Based Approach
Sort the citations array in descending order and find the largest index where citations[i] >= i+1.
**Time:** O(n log n) due to sorting · **Space:** O(1) if in-place sorting is used
**Pros:** More efficient than brute force; Easy to understand; Works well for most inputs
**Cons:** Modifies input array; Still not optimal; Requires sorting
### Explanation
1. Sort the array in descending order
2. Find the largest index i where citations[i] >= i+1
3. The h-index will be i+1

```java
public int hIndex(int[] citations) {
    Arrays.sort(citations);
    int n = citations.length;
    
    // Convert to descending order problem
    for (int i = 0; i < n/2; i++) {
        int temp = citations[i];
        citations[i] = citations[n-1-i];
        citations[n-1-i] = temp;
    }
    
    for (int i = 0; i < n; i++) {
        if (citations[i] < i + 1) {
            return i;
        }
    }
    return n;
}
```
### Algorithm
1. Sort array in descending order
2. For i from 0 to n-1:
   - If citations[i] < i+1, return i
3. Return n if no solution found

## Counting Sort Approach
Use counting sort technique to count papers for each citation number and then find the h-index by accumulating counts from highest to lowest.
**Time:** O(n) where n is the length of citations array · **Space:** O(n) for the count array
**Pros:** Most efficient solution; Doesn't modify input array; Works in linear time
**Cons:** Uses extra space; Might not be intuitive at first
### Explanation
1. Create a count array to store frequency of citations
2. Count papers for each citation number
3. Accumulate counts from highest to lowest until we find h-index

```java
public int hIndex(int[] citations) {
    int n = citations.length;
    int[] count = new int[n + 1];
    
    // Count papers for each citation number
    for (int citation : citations) {
        if (citation >= n) {
            count[n]++;
        } else {
            count[citation]++;
        }
    }
    
    // Find h-index by accumulating counts
    int total = 0;
    for (int i = n; i >= 0; i--) {
        total += count[i];
        if (total >= i) {
            return i;
        }
    }
    
    return 0;
}
```
### Algorithm
1. Create count array of size n+1
2. Count papers for each citation
3. Accumulate counts from highest to lowest
4. Return first i where accumulated count >= i

# Solutions
### Java

```java
class Solution {
public
  int hIndex(int[] citations) {
    int n = citations.length;
    int[] cnt = new int[n + 1];
    for (int x : citations) {
      ++cnt[Math.min(x, n)];
    }
    for (int h = n, s = 0;; --h) {
      s += cnt[h];
      if (s >= h) {
        return h;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int hIndex(vector<int> &citations) {
    int n = citations.size();
    int cnt[n + 1];
    memset(cnt, 0, sizeof(cnt));
    for (int x : citations) {
      ++cnt[min(x, n)];
    }
    for (int h = n, s = 0;; --h) {
      s += cnt[h];
      if (s >= h) {
        return h;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def hIndex(self, citations: List[int]) -> int: n = len(citations) cnt = [0] * (n + 1) for x in citations: cnt[min(x, n)] += 1 s = 0 for h in range(n, - 1, - 1): s += cnt[h] if s >= h: return h

```