H-Index

Medium
207.

H-Index

H-Index is a medium coding problem on arrays, sorting and counting sort, asked in Amazon, Google, Meta and Bloomberg interviews.

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

The h-index is the largest h such that the 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
Three papers have at least 3 citations each; there are not four papers with at least 4.

Example 2

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

Example 3

Input
citations = [0,0]
Output
0

Constraints

  • 1 <= citations.length <= 40
  • 0 <= citations[i] <= 1000

Follow-up: Sorting makes it O(n log n). Counting makes it O(n).

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

H-Index — Solution in Python, Java & C++

H-Index solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

H-Index is a medium coding problem on arrays, sorting and counting sort, asked in Amazon, Google, Meta and Bloomberg interviews.

Problem statement

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

The h-index is the largest h such that the 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: Three papers have at least 3 citations each; there are not four papers with at least 4.

Example 2

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

Example 3

Input: citations = [0,0]
Output: 0

Constraints

  • 1 <= citations.length <= 40
  • 0 <= citations[i] <= 1000

Follow-up: Sorting makes it O(n log n). Counting makes it O(n).

Hints for H-Index

  1. Hint 1

    Sort the citations in descending order.

  2. Hint 2

    After sorting, the paper at 0-based index i is the (i + 1)-th best; if it still has i + 1 citations, an h-index of i + 1 is achievable.

  3. Hint 3

    Take the largest such i + 1 — the condition can turn on and off, so do not stop at the first failure without checking.

How to solve H-Index

Sort descending; the paper at 0-based index i is the (i + 1)-th best, and if it has at least i + 1 citations then h = i + 1 is achievable. Take the largest such i + 1.

Approach

  1. Sort citations in descending order.
  2. For each i, if ordered[i] >= i + 1, set h = i + 1.
  3. Return h.

Why it works

In descending order the first i + 1 papers all have at least ordered[i] citations, so the condition certifies h = i + 1. The condition is monotone — once it fails it stays failed — so the last success is the maximum.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • A bucket count over 0..n gives O(n).
  • An all-zero array has h-index 0.

Reference solution

Python

def hIndex(citations):
    ordered = sorted(citations, reverse=True)
    h = 0
    for i, c in enumerate(ordered):
        if c >= i + 1:
            h = i + 1
    return h

Java

public static int hIndex(int[] citations) {
    int[] ordered = Arrays.copyOf(citations, citations.length);
    Arrays.sort(ordered);
    int n = ordered.length;
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (ordered[n - 1 - i] >= i + 1) h = i + 1;
    }
    return h;
}

C++

int hIndex(vector<int>& citations) {
    vector<int> ordered = citations;
    sort(ordered.begin(), ordered.end(), greater<int>());
    int h = 0;
    for (int i = 0; i < (int) ordered.size(); i++) {
        if (ordered[i] >= i + 1) h = i + 1;
    }
    return h;
}

JavaScript

var hIndex = function(citations) {
    const ordered = citations.slice().sort(function(a, b) { return b - a; });
    let h = 0;
    for (let i = 0; i < ordered.length; i++) {
        if (ordered[i] >= i + 1) h = i + 1;
    }
    return h;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms