H-Index II - Practice Coding Problems

H-Index II - Problem

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i-th paper and citations is sorted in non-descending order, 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.

You must write an algorithm that runs in logarithmic time.

Input & Output

Example 1 — Standard Case

$ Input: citations = [0,1,3,5,6]

› Output: 3

💡 Note: The researcher has 5 papers with [0,1,3,5,6] citations. 3 papers have at least 3 citations each (papers with 3,5,6 citations), and the other 2 papers have ≤ 3 citations. So h-index is 3.

Example 2 — Higher Citations

$ Input: citations = [1,2,100]

› Output: 2

💡 Note: The researcher has 3 papers with [1,2,100] citations. 2 papers have at least 2 citations each (papers with 2,100 citations), and 1 paper has ≤ 2 citations. So h-index is 2.

Example 3 — All Zero Citations

$ Input: citations = [0,0]

› Output: 0

💡 Note: Both papers have 0 citations, so no papers have at least 1 citation. H-index is 0.

Constraints

1 ≤ citations.length ≤ 10⁵
0 ≤ citations[i] ≤ 1000
citations is sorted in non-descending order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted citations array [0,1,3,5,6]

Process

Find maximum h where ≥h papers have ≥h citations

Output

H-index is 3

Key Takeaway

🎯 Key Insight: Use binary search on the answer since array is sorted - we can check validity in O(1)

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to use binary search on the answer space since the array is sorted. Best approach is binary search which finds the maximum valid h-index efficiently. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search	O(log n)	O(1)	Binary search on the answer to achieve O(log n) time
Linear Search	O(n²)	O(1)	Check each possible h-index from n down to 1
Optimized Linear Scan	O(n)	O(1)	Single pass using the fact that array is sorted

Binary Search — Algorithm Steps

Binary search on h-index values from 0 to n
For each mid value, check if it's a valid h-index
If valid, try larger h; if invalid, try smaller h

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Range

Search h-index from 0 to 5

Mid=3

Check if h=3 is valid

Found Answer

h=3 is maximum valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* citations, int n) {
    int left = 0, right = n;
    
    while (left < right) {
        int mid = (left + right + 1) / 2;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (citations[i] >= mid) {
                count = n - i;
                break;
            }
        }
        
        if (count >= mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int citations[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        citations[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    int result = solution(citations, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search divides the search space in half each iteration

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few variables for binary search bounds

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler