H-Index (Sort + Binary Search)

📋

Problem

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.

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

Edge cases: All zero citations → h-index is 0All citations equal and large → h-index equals number of papersSingle paper with zero citations → h-index is 0

</>

IDE

def hIndex(citations: list[int]) -> int:public int hIndex(int[] citations)int hIndex(vector<int> citations)function hIndex(citations)

def hIndex(citations):
    # Write your solution here
    pass

class Solution {
    public int hIndex(int[] citations) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int hIndex(vector<int> citations) {
    // Write your solution here
    return 0;
}

function hIndex(citations) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 4Greedy approach returns first h where citations[h-1] >= h instead of maximum h.✅ Iterate through all h from 1 to n and return the maximum h satisfying citations[h-1] >= h.

Wrong: 5Confusing total number of papers with h-index; ignoring citations[h-1] >= h condition.✅ Check condition citations[h-1] >= h for each h and return max valid h.

Wrong: 1Off-by-one error causing undercounting h-index on boundary cases.✅ Ensure condition citations[h-1] >= h is checked correctly for all h.

Wrong: Non-zero for empty inputNo check for empty input array.✅ Return 0 immediately if citations array is empty.

Wrong: TimeoutUsing brute force O(n^2) approach on large inputs.✅ Use sorting plus binary search or linear scan to achieve O(n log n) time.

✓

Test Cases

Try testing your solution on empty and single-element arrays to handle base cases.

Consider tricky inputs where greedy or off-by-one errors might occur.

Optimize your solution to avoid timeouts on large inputs by using sorting and binary search.

t1_01basic

Input{"citations":[3,0,6,1,5]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Sort the citations array in descending order to analyze counts easily.

💡 Check for the largest h where citations[h-1] >= h.

💡 Return the maximum h such that citations[h-1] >= h.

Why it failed: Incorrect output means sorting or counting logic is wrong. Fix by sorting descending and checking citations[h-1] >= h.

✓ Correctly computed h-index using sorting and counting.

t1_02basic

Input{"citations":[10,8,5,4,3]}

Expected4

⏱ Performance - must finish in 2000ms

Sorted descending: [10,8,5,4,3]. 4 papers have at least 4 citations.

💡 Sort citations descending to align papers by citation count.

💡 Find max h where citations[h-1] >= h.

💡 Check each position h from 1 to n to find max valid h.

Why it failed: If output is less than 4, likely failed to check all h or miscounted. Fix by iterating h from 1 to n and verifying citations[h-1] >= h.

✓ Correctly identified h-index by checking sorted citations.

t2_01edge

Input{"citations":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no papers, so h-index is 0.

💡 Consider the case when there are no papers.

💡 The h-index must be 0 if citations array is empty.

💡 Return 0 immediately if citations list is empty.

Why it failed: Returning non-zero means code does not handle empty input. Fix by checking if citations is empty and return 0.

✓ Correctly returns 0 for empty citations array.

t2_02edge

Input{"citations":[0]}

Expected0

⏱ Performance - must finish in 2000ms

Single paper with zero citations means h-index is 0.

💡 Check single element arrays carefully.

💡 If citation count is less than 1, h-index is 0.

💡 Return 0 if citations[0] < 1 for single paper.

Why it failed: Returning 1 or more means code incorrectly assumes any paper counts. Fix by verifying citations[0] >= 1 before returning 1.

✓ Correctly returns 0 for single zero citation.

t2_03edge

Input{"citations":[10000,10000,10000]}

Expected3

⏱ Performance - must finish in 2000ms

All citations equal and large; h-index equals number of papers (3).

💡 When all citations are large, h-index can be total papers.

💡 Check if citations[i] >= n for all i.

💡 Return n if all citations >= n.

Why it failed: If output less than n, code fails to handle all large citations. Fix by checking if citations[n-1] >= n after sorting descending.

✓ Correctly returns h-index equal to number of papers when all citations are large.

t3_01corner

Input{"citations":[0,1,3,5,6]}

Expected3

⏱ Performance - must finish in 2000ms

Sorted descending: [6,5,3,1,0]. h-index is 3, not 4.

💡 Beware of greedy approach that picks first h where citations[h-1] >= h.

💡 Check all h values to find maximum valid h, not just first valid.

💡 Iterate through all h and pick max h with citations[h-1] >= h.

Why it failed: Greedy approach returns 4 incorrectly. Fix by scanning all h values and returning max valid h.

✓ Correctly avoids greedy trap and finds max h-index.

t3_02corner

Input{"citations":[1,1,1,1,1]}

Expected1

⏱ Performance - must finish in 2000ms

All citations equal to 1; h-index is 1, not 5.

💡 Do not confuse total papers with h-index.

💡 Check that citations[h-1] >= h for each h.

💡 Return max h where citations[h-1] >= h, here h=1 only.

Why it failed: Mistakenly returning 5 means ignoring citations[h-1] >= h condition. Fix by verifying condition for each h.

✓ Correctly computes h-index for uniform low citations.

t3_03corner

Input{"citations":[4,4,0,0]}

Expected2

⏱ Performance - must finish in 2000ms

Sorted descending: [4,4,0,0]. h-index is 2, not 4 or 0.

💡 Check boundary where h equals number of papers with citations >= h.

💡 Verify citations[h-1] >= h for each h.

💡 Return max h satisfying condition; here h=2 only.

Why it failed: Returning 4 or 0 means off-by-one or boundary check error. Fix by careful condition check citations[h-1] >= h.

✓ Correctly handles exact boundary condition.

t4_01performance

Input{"citations":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, citations sorted descending from 10000 down. O(n log n) or better must complete within 2s.

💡 Sorting plus binary search or linear scan is efficient for n=100.

💡 Avoid brute force O(n^2) which times out for large n.

💡 Use binary search on h or linear scan after sorting descending.

Why it failed: Brute force O(n^2) approach times out on large input. Fix by using sorting plus binary search or linear scan O(n log n).

✓ Efficient O(n log n) or better approach confirmed by passing performance test.

Practice

1. You are given two integer arrays where the first array needs to be sorted such that the relative order of items in the first array follows the order defined by the second array. Elements not present in the second array should be placed at the end in ascending order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by repeatedly selecting the smallest element from the first array that appears in the second array

B. Brute force nested loops checking each element of the first array against the second array

C. Dynamic programming to find the longest subsequence matching the order of the second array

D. Counting sort based on frequency arrays combined with the order defined by the second array

Solution

1. Step 1: Understand problem constraints

   The problem requires sorting the first array so that elements appear in the order defined by the second array, with leftover elements sorted ascending at the end.

2. Step 2: Identify optimal approach

   Counting sort using frequency arrays efficiently counts occurrences and outputs elements in the required order in O(n + k) time, where k is max element value.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Counting sort matches problem constraints and is optimal for integer ranges [OK]

Hint: Frequency counting suits custom order sorting [OK]

Common Mistakes:

• Assuming greedy selection suffices without frequency counting
• Confusing this with subsequence or DP problems
• Using brute force nested loops which is inefficient

2. Consider the following Python code that sorts a matrix diagonally using min-heaps. What is the final matrix returned when the input is [[3,3,1,1],[2,2,1,2],[1,1,1,2]]?

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i - j], mat[i][j])
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])
    return mat

matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
print(diagonalSort(matrix))

easy

A. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

B. [[1,1,1,1],[1,2,2,2],[1,1,3,3]]

C. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

D. [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

Solution

1. Step 1: Build min-heaps keyed by diagonal (row - col)

   For each element, push into heap keyed by i - j. For example, diagonal key 0 has elements [3,2,1], which heapify to [1,2,3].

2. Step 2: Pop from heaps to replace matrix elements

   Traverse matrix again, replacing each element with the smallest from its diagonal heap. This sorts each diagonal ascending.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys and heaps produce sorted diagonals matching [[1,1,1,1],[1,2,2,2],[1,2,3,3]] [OK]

Hint: Heap per diagonal ensures sorted order on replacement [OK]

Common Mistakes:

• Off-by-one errors in heap keys
• Mixing up heap push/pop order
• Incorrectly reconstructing matrix from heaps

3. Given the following code snippet implementing the optimal wiggle sort, what is the content of the array nums after the while loop completes when the input is [1, 3, 2]?

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 1, 2]

D. [1, 2, 3]

Solution

1. Step 1: Sort and find median

   Sorted nums = [1, 2, 3], median = nums[(3-1)//2] = nums[1] = 2.

2. Step 2: Apply virtual indexing and partition

   Virtual indices for i=0,1,2 are (1+2*0)%3=1, (1+2*1)%3=0, (1+2*2)%3=2. - i=0: nums[1]=2 equals median -> i=1 - i=1: nums[0]=1 less than median -> swap with nums[virtual_index(right=2)]=nums[2]=3, right=1 - After swap: nums=[3,2,1], i=1, right=1 - i=1: nums[0]=3 greater than median -> swap with nums[virtual_index(left=0)]=nums[1]=2, left=1, i=2 - Final nums=[2,3,1]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final array satisfies wiggle property: 2 < 3 > 1 [OK]

Hint: Trace virtual indices carefully to get final array [OK]

Common Mistakes:

• Confusing virtual index mapping
• Off-by-one in median calculation
• Not updating pointers correctly

4. Consider the following buggy code snippet for finding missing ranges. Which line contains the subtle bug that causes missing ranges at the start of the interval to be ignored?

medium

A. Line with condition 'if pointer <= curr:' should be 'if pointer < curr:'

B. Line updating pointer to 'curr + 1' should be 'curr' instead

C. Line checking 'if idx == len(nums):' should check 'if idx > len(nums):'

D. Line appending missing range should format single numbers as 'start->end' always

Solution

1. Step 1: Identify condition for missing range detection

   The condition 'if pointer <= curr:' incorrectly includes the case pointer == curr, causing no gap detection before first element if pointer equals first number.

2. Step 2: Correct condition to 'if pointer < curr:'

   This ensures missing ranges are detected only when pointer is strictly less than current number, capturing missing numbers before first element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes missing start ranges [OK]

Hint: Check strict inequality when detecting gaps [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect pointer update
• Wrong formatting of single numbers

5. Suppose the problem is modified so that elements can be reused unlimited times to form an infinitely long array with no two adjacent elements equal. Which modification to the heap-based algorithm correctly handles this variant?

hard

A. Remove the max frequency check and keep pushing elements back with updated counts indefinitely.

B. Use a queue instead of a heap to cycle through elements ensuring no two adjacent are equal.

C. Use a max heap but reset counts to original frequencies after each full pass through the heap.

D. Modify the algorithm to never decrement counts and always push elements back to allow infinite reuse.

Solution

1. Step 1: Understand infinite reuse implication

   Since elements can be reused unlimited times, counts do not decrease; the algorithm must allow repeated placement without decrementing counts.

2. Step 2: Modify heap usage accordingly

   Never decrement counts and always push elements back to heap to maintain availability, ensuring no two adjacent elements are equal.

3. Step 3: Evaluate other options

   Removing max frequency check or resetting counts breaks correctness or efficiency; queue does not prioritize frequency.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Maintaining counts without decrement allows infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means counts stay constant [OK]

Common Mistakes:

• Removing checks without adjusting counts
• Resetting counts causing incorrect order