H-Index (Sort + Binary Search)

🎯

H-Index (Sort + Binary Search)

mediumSORT_SEARCHAmazonGoogleFacebook

Imagine a researcher wants to measure their impact by counting how many papers have at least that many citations. This metric, called the H-Index, helps quantify influence in academia.

💡 This problem requires understanding how sorting can help organize data to enable efficient searching. Beginners often struggle because the H-Index definition is subtle and the direct brute force approach is inefficient. Understanding how sorting and binary search interplay is key.

📋

Problem Statement

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, compute the researcher's h-index. The h-index is defined as the maximum value h such that the researcher has published h papers that have each been cited at least h times. Return the h-index.

1 ≤ n ≤ 10^50 ≤ citations[i] ≤ 10^4

💡

Example

Input"[3, 0, 6, 1, 5]"

Output3

Sorted descending: [6,5,3,1,0]. There are 3 papers with at least 3 citations.

• All zero citations → h-index is 0
• All citations equal and large → h-index equals number of papers
• Single paper with zero citations → h-index is 0
• Single paper with citations > 0 → h-index is 1

⚠️

Common Mistakes

Misunderstanding h-index definition and off-by-one errors

Returns incorrect h-index, often off by 1

✅ Carefully use 1-based indexing when comparing citations[i] to i+1

Not sorting before binary search or linear scan

Incorrect results because order matters for the condition

✅ Always sort citations descending (or ascending and scan from end) before checking

Counting papers inefficiently inside binary search without early break

Unnecessary full scans cause slower runtime

✅ Break counting loop early when citations[i] < mid to save time

Using brute force for large inputs

Time limit exceeded, interviewers see lack of optimization

✅ Explain brute force but implement sorting + linear scan or binary search

🧠

Brute Force (Check All Possible h Values)

💡 This approach exists to build intuition by directly applying the h-index definition without optimization. It helps beginners understand the problem deeply before moving to efficient methods.

Intuition

Try every possible h from 0 up to the number of papers, count how many papers have at least h citations, and check if that count is at least h.

Algorithm

1. Initialize max_h to 0.
2. For each h from 0 to n (number of papers):
3. Count how many papers have citations >= h.
4. If count >= h, update max_h to h.
5. Return max_h.

💡 This algorithm is straightforward but inefficient because it checks every possible h and counts papers each time, leading to repeated work.

</>

Code

def hIndex(citations):
    n = len(citations)
    max_h = 0
    for h in range(n + 1):
        count = 0
        for c in citations:
            if c >= h:
                count += 1
        if count >= h:
            max_h = h
    return max_h

# Driver code
if __name__ == '__main__':
    print(hIndex([3,0,6,1,5]))  # Output: 3

Line Notes

n = len(citations)Determine total number of papers to set h range

for h in range(n + 1)Try every possible h from 0 to n inclusive

for c in citationsCount how many papers have citations >= current h

if count >= hCheck if current h satisfies the h-index condition

public class Solution {
    public static int hIndex(int[] citations) {
        int n = citations.length;
        int maxH = 0;
        for (int h = 0; h <= n; h++) {
            int count = 0;
            for (int c : citations) {
                if (c >= h) count++;
            }
            if (count >= h) maxH = h;
        }
        return maxH;
    }

    public static void main(String[] args) {
        int[] citations = {3,0,6,1,5};
        System.out.println(hIndex(citations)); // Output: 3
    }
}

Line Notes

int n = citations.length;Get number of papers to define h range

for (int h = 0; h <= n; h++)Iterate over all possible h values

for (int c : citations)Count papers with citations >= h

if (count >= h) maxH = h;Update maxH if condition holds

#include <iostream>
#include <vector>
using namespace std;

int hIndex(vector<int>& citations) {
    int n = citations.size();
    int maxH = 0;
    for (int h = 0; h <= n; h++) {
        int count = 0;
        for (int c : citations) {
            if (c >= h) count++;
        }
        if (count >= h) maxH = h;
    }
    return maxH;
}

int main() {
    vector<int> citations = {3,0,6,1,5};
    cout << hIndex(citations) << endl; // Output: 3
    return 0;
}

Line Notes

int n = citations.size();Determine number of papers for h range

for (int h = 0; h <= n; h++)Check all possible h values

for (int c : citations)Count papers with citations >= h

if (count >= h) maxH = h;Update maxH if condition is met

function hIndex(citations) {
    const n = citations.length;
    let maxH = 0;
    for (let h = 0; h <= n; h++) {
        let count = 0;
        for (const c of citations) {
            if (c >= h) count++;
        }
        if (count >= h) maxH = h;
    }
    return maxH;
}

// Test
console.log(hIndex([3,0,6,1,5])); // Output: 3

Line Notes

const n = citations.length;Get total papers to define h range

for (let h = 0; h <= n; h++)Try every possible h value

for (const c of citations)Count papers with citations >= h

if (count >= h) maxH = h;Update maxH if condition holds

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each h (up to n), we count papers with citations >= h, which takes O(n), so total O(n^2).

💡 For n=20, this means about 400 operations, which is okay, but for n=100000 it becomes 10 billion operations, too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Sorting + Linear Scan

💡 Sorting the citations array descending allows us to check the h-index condition in a single pass, improving efficiency drastically.

Intuition

Sort citations descending. The h-index is the maximum i where citations[i] >= i+1 (1-based). We scan from highest to lowest to find this.

Algorithm

1. Sort citations in descending order.
2. Initialize h to 0.
3. Iterate over sorted citations with index i:
4. If citations[i] >= i+1, update h to i+1.
5. Else break the loop.
6. Return h.

💡 Sorting organizes data so the condition can be checked by comparing citation count to position, avoiding repeated counting.

</>

Code

def hIndex(citations):
    citations.sort(reverse=True)
    h = 0
    for i, c in enumerate(citations):
        if c >= i + 1:
            h = i + 1
        else:
            break
    return h

# Driver code
if __name__ == '__main__':
    print(hIndex([3,0,6,1,5]))  # Output: 3

Line Notes

citations.sort(reverse=True)Sort papers descending by citations to enable linear check

for i, c in enumerate(citations)Iterate with index to compare citation count to position

if c >= i + 1Check if current paper meets h-index condition

else: breakStop early when condition fails to save time

import java.util.Arrays;

public class Solution {
    public static int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;
        for (int i = n - 1; i >= 0; i--) {
            int pos = n - i;
            if (citations[i] >= pos) h = pos;
            else break;
        }
        return h;
    }

    public static void main(String[] args) {
        int[] citations = {3,0,6,1,5};
        System.out.println(hIndex(citations)); // Output: 3
    }
}

Line Notes

Arrays.sort(citations);Sort ascending to scan from end for descending order

for (int i = n - 1; i >= 0; i--)Iterate from highest citation to lowest

int pos = n - i;Calculate 1-based position in descending order

if (citations[i] >= pos) h = pos;Update h if condition holds

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int hIndex(vector<int>& citations) {
    sort(citations.begin(), citations.end());
    int n = citations.size();
    int h = 0;
    for (int i = n - 1; i >= 0; i--) {
        int pos = n - i;
        if (citations[i] >= pos) h = pos;
        else break;
    }
    return h;
}

int main() {
    vector<int> citations = {3,0,6,1,5};
    cout << hIndex(citations) << endl; // Output: 3
    return 0;
}

Line Notes

sort(citations.begin(), citations.end());Sort ascending to scan from end for descending order

for (int i = n - 1; i >= 0; i--)Iterate from highest citation to lowest

int pos = n - i;Calculate position in descending order

if (citations[i] >= pos) h = pos;Update h if condition holds

function hIndex(citations) {
    citations.sort((a,b) => a - b);
    const n = citations.length;
    let h = 0;
    for (let i = n - 1; i >= 0; i--) {
        let pos = n - i;
        if (citations[i] >= pos) h = pos;
        else break;
    }
    return h;
}

// Test
console.log(hIndex([3,0,6,1,5])); // Output: 3

Line Notes

citations.sort((a,b) => a - b);Sort ascending to scan from end for descending order

for (let i = n - 1; i >= 0; i--)Iterate from highest citation to lowest

let pos = n - i;Calculate 1-based position in descending order

if (citations[i] >= pos) h = pos;Update h if condition holds

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort implementation

Sorting takes O(n log n), then a single pass O(n) to find h-index.

💡 For n=100000, sorting is feasible (~1.5 million operations), making this approach practical.

Interview Verdict: Accepted

This approach is efficient and simple enough to implement in interviews, often the preferred solution.

🧠

Sorting + Binary Search on h

💡 Binary search on h-index values leverages the sorted array to find the maximum h efficiently, combining sorting and binary search skills.

Intuition

Sort citations descending. Use binary search on h from 0 to n. For each mid h, check if there are at least h papers with citations >= h. Narrow search accordingly.

Algorithm

1. Sort citations in descending order.
2. Set low = 0, high = n (number of papers).
3. While low <= high:
4. mid = (low + high) // 2
5. Count how many papers have citations >= mid.
6. If count >= mid, set low = mid + 1 (try higher h).
7. Else set high = mid - 1 (try lower h).
8. Return high as the maximum valid h.

💡 Binary search reduces the number of checks drastically by halving the search space each time, making it efficient for large inputs.

</>

Code

def hIndex(citations):
    citations.sort(reverse=True)
    n = len(citations)
    low, high = 0, n
    while low <= high:
        mid = (low + high) // 2
        count = 0
        for c in citations:
            if c >= mid:
                count += 1
            else:
                break
        if count >= mid:
            low = mid + 1
        else:
            high = mid - 1
    return high

# Driver code
if __name__ == '__main__':
    print(hIndex([3,0,6,1,5]))  # Output: 3

Line Notes

citations.sort(reverse=True)Sort descending to enable early break in counting

low, high = 0, nInitialize binary search boundaries for h

mid = (low + high) // 2Calculate middle h to test

if count >= midIf enough papers meet mid, try higher h

import java.util.Arrays;

public class Solution {
    public static int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int low = 0, high = n;
        while (low <= high) {
            int mid = (low + high) / 2;
            int count = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (citations[i] >= mid) count++;
                else break;
            }
            if (count >= mid) low = mid + 1;
            else high = mid - 1;
        }
        return high;
    }

    public static void main(String[] args) {
        int[] citations = {3,0,6,1,5};
        System.out.println(hIndex(citations)); // Output: 3
    }
}

Line Notes

Arrays.sort(citations);Sort ascending to scan from end for descending order

int low = 0, high = n;Set binary search range for h

for (int i = n - 1; i >= 0; i--)Count papers with citations >= mid

if (count >= mid) low = mid + 1;Try higher h if condition holds

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int hIndex(vector<int>& citations) {
    sort(citations.begin(), citations.end());
    int n = citations.size();
    int low = 0, high = n;
    while (low <= high) {
        int mid = (low + high) / 2;
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (citations[i] >= mid) count++;
            else break;
        }
        if (count >= mid) low = mid + 1;
        else high = mid - 1;
    }
    return high;
}

int main() {
    vector<int> citations = {3,0,6,1,5};
    cout << hIndex(citations) << endl; // Output: 3
    return 0;
}

Line Notes

sort(citations.begin(), citations.end());Sort ascending to scan from end for descending order

int low = 0, high = n;Initialize binary search range

for (int i = n - 1; i >= 0; i--)Count papers with citations >= mid

if (count >= mid) low = mid + 1;Adjust low to search higher h

function hIndex(citations) {
    citations.sort((a,b) => a - b);
    const n = citations.length;
    let low = 0, high = n;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        let count = 0;
        for (let i = n - 1; i >= 0; i--) {
            if (citations[i] >= mid) count++;
            else break;
        }
        if (count >= mid) low = mid + 1;
        else high = mid - 1;
    }
    return high;
}

// Test
console.log(hIndex([3,0,6,1,5])); // Output: 3

Line Notes

citations.sort((a,b) => a - b);Sort ascending to scan from end for descending order

let low = 0, high = n;Set binary search boundaries

for (let i = n - 1; i >= 0; i--)Count papers with citations >= mid

if (count >= mid) low = mid + 1;Try higher h if condition holds

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort

Sorting is O(n log n). Each binary search iteration counts papers in O(n). With O(log n) iterations, total O(n log n).

💡 For n=100000, this is efficient enough, but the linear count inside binary search can be optimized further.

Interview Verdict: Accepted

This approach is efficient and demonstrates mastery of binary search combined with sorting, a common interview pattern.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (Sorting + Linear Scan) is the best balance of simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Sorting + Linear Scan	O(n log n)	O(1) or O(n)	No	N/A	Code this approach in 95% of interviews
3. Sorting + Binary Search	O(n log n)	O(1) or O(n)	No	N/A	Mention as optimization, code if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm understanding of h-index definition.Step 2: Present the brute force approach to show understanding of the problem.Step 3: Explain sorting and linear scan approach for efficiency.Step 4: Discuss binary search optimization on h-index values.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of sorting, binary search, and ability to optimize brute force solutions.

Common Follow-ups

• What if citations are already sorted? → Use binary search directly without sorting.
• Can you solve in O(n) time? → Yes, using counting sort or bucket sort approach.

💡 Follow-ups test your ability to adapt solutions to constraints and optimize further.

🔍

Pattern Recognition

When to Use

1) Problem involves a threshold or count condition, 2) Data can be sorted, 3) Need to find maximum/minimum satisfying condition, 4) Binary search can be applied on answer range.

Signature Phrases

'maximum h such that at least h papers have h citations''find the largest number meeting a count condition'

NOT This Pattern When

Problems that require DP or greedy without sorting or binary search are different.

Similar Problems

Kth Largest Element - also uses sorting and binary searchCapacity To Ship Packages Within D Days - binary search on answer

Practice

1. You are given an array of integers and need to rearrange it so that no two adjacent elements are the same. Which approach guarantees an optimal solution for this problem?

easy

A. Count frequencies, then use a max heap to greedily place the most frequent elements first, ensuring spacing.

B. Use backtracking to generate all permutations and check for valid arrangements.

C. Sort the array and then swap adjacent elements to avoid duplicates.

D. Use dynamic programming to track valid sequences avoiding adjacent duplicates.

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging elements so no two adjacent are equal, which demands careful placement of frequent elements.

2. Step 2: Identify approach that handles frequency and spacing

   Using a max heap to always pick the most frequent element available and placing it ensures no two identical elements are adjacent, which brute force or simple sorting cannot guarantee efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach handles frequency and spacing correctly [OK]

Hint: Max heap ensures spacing of frequent elements [OK]

Common Mistakes:

• Thinking sorting alone avoids adjacent duplicates
• Assuming DP solves this without frequency tracking

2. You are given a list of time points in 24-hour format (e.g., "23:59", "00:00") and need to find the minimum difference in minutes between any two time points, considering the circular nature of the clock (i.e., times wrap around midnight). Which approach guarantees an optimal solution for this problem?

easy

A. Sort the times converted to minutes, then find the minimum difference between adjacent times including the circular pair (last and first).

B. Use a brute force nested loop to compare all pairs of times and compute their differences.

C. Use dynamic programming to store minimum differences while iterating through the times.

D. Apply a greedy algorithm that picks the closest time pairs without sorting.

Solution

1. Step 1: Understand the circular nature of time

   Since times wrap around midnight, the minimum difference might be between the last and first times after sorting.

2. Step 2: Sort and check adjacent differences including circular pair

   Sorting times converted to minutes allows a single pass to find minimum adjacent differences, including the circular pair, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting enables O(n log n) solution that correctly handles circular wrap [OK]

Hint: Sort times and check adjacent pairs including wrap [OK]

Common Mistakes:

• Using brute force is too slow for large inputs
• Ignoring circular difference between last and first times
• Trying greedy without sorting fails on wrap-around

3. You are given an unsorted array of integers and need to reorder it so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4] and so on, ensuring a "wiggle" pattern. Which approach guarantees an optimal solution that runs in O(n log n) time and uses O(1) extra space?

easy

A. Use a greedy approach by swapping adjacent elements whenever the wiggle property is violated.

B. Sort the array, find the median, then rearrange elements in-place using virtual indexing and three-way partitioning.

C. Use dynamic programming to find the longest wiggle subsequence and reconstruct the array accordingly.

D. Sort the array and then alternate picking elements from the start and end into a new array.

Solution

1. Step 1: Understand the wiggle property requirements

   The problem requires elements to be reordered so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4]..., which is not guaranteed by simple sorting or greedy swaps.

2. Step 2: Identify the approach that ensures correct interleaving

   Sorting and then using the median with virtual indexing and three-way partitioning ensures elements greater than median are placed at odd indices and smaller at even indices, maintaining the wiggle property in O(n log n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Virtual indexing and median partitioning guarantee wiggle order [OK]

Hint: Virtual indexing with median partitioning ensures wiggle order [OK]

Common Mistakes:

• Assuming greedy swaps fix all cases
• Using DP for rearrangement instead of subsequence
• Ignoring in-place rearrangement for space efficiency

4. Consider the following buggy implementation of wiggle sort. Which line contains the subtle bug that causes the algorithm to fail on inputs with duplicates?

medium

A. Line 9: def virtual_index(i): return (1 + 2 * i) % (n | 1)

B. Line 3: nums.sort()

C. Line 4: median = nums[n // 2]

D. Line 15: elif nums[vi] < median:

Solution

1. Step 1: Identify median calculation

   The median is incorrectly chosen as nums[n // 2], which is the upper median for even-length arrays, but the algorithm requires the lower median nums[(n - 1) // 2].

2. Step 2: Understand impact on partitioning

   Incorrect median causes wrong partitioning of elements equal to median, leading to clustering and violation of wiggle property especially with duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct median index is (n - 1) // 2, not n // 2 [OK]

Hint: Median index off-by-one breaks partitioning with duplicates [OK]

Common Mistakes:

• Using n//2 instead of (n-1)//2 for median
• Ignoring duplicates in partitioning
• Misusing virtual indexing

5. Suppose the problem is modified so that numbers can be reused unlimited times to form the largest number (e.g., from [3, 30, 34], you can use '3' multiple times). Which of the following approaches correctly adapts the solution?

hard

A. Generate all permutations with repetition allowed and select the maximum concatenation.

B. Use a greedy approach repeatedly picking the number that maximizes the next concatenation until length limit is reached.

C. Use the same custom comparator sort on the original list and concatenate all elements once.

D. Sort numbers with custom comparator and then repeatedly append the first element until desired length.

Solution

1. Step 1: Understand reuse implication

   Unlimited reuse means infinite permutations; brute force is infeasible.

2. Step 2: Identify correct approach

   A greedy approach that picks the number which maximizes concatenation at each step is needed to build the largest number incrementally.

3. Step 3: Why other options fail

   Sorting once and concatenating once ignores reuse; brute force with repetition is exponential; appending first element repeatedly ignores other candidates.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Greedy incremental selection handles reuse correctly [OK]

Hint: Reuse requires greedy incremental selection, not one-time sort [OK]

Common Mistakes:

• Assuming original sort suffices for reuse scenario