H-Index (Sort + Binary Search)

▶

Steps

setup

Start with the original citations array

We begin with the input array of citations: [3, 0, 6, 1, 5]. This is the unsorted data representing citation counts per paper.

💡 Seeing the original data helps understand why sorting is necessary to apply binary search effectively.

Line:

citations = [3, 0, 6, 1, 5]

💡 The input array is unordered, which makes direct binary search impossible.

setup

Sort citations in descending order

We sort the citations array in descending order to prepare for binary search. The sorted array is [6, 5, 3, 1, 0].

💡 Sorting arranges the data so that we can efficiently check how many papers have at least 'mid' citations.

Line:

citations.sort(reverse=True)

💡 Descending order allows counting papers with citations >= mid by scanning from the start.

setup

Initialize binary search bounds

Set low = 0 and high = 5 (number of papers). These pointers define the search range for possible h-index values.

💡 Binary search requires initial low and high bounds to start narrowing down the h-index.

Line:

n = len(citations)
low, high = 0, n

💡 The h-index must be between 0 and the total number of papers.

compare

Calculate mid = (low + high) // 2

Calculate mid as the midpoint of low and high: mid = (0 + 5) // 2 = 2. This is the candidate h-index to test.

💡 Midpoint divides the search space to test if h = mid is valid.

Line:

mid = (low + high) // 2

💡 Mid is the current guess for the h-index.

compare

Count papers with citations >= mid (2)

Start counting papers from the beginning that have citations >= 2. We check each paper until we find one with fewer citations.

💡 Counting how many papers meet or exceed mid is key to validating if mid can be the h-index.

Line:

count = 0
for c in citations:
    if c >= mid:
        count += 1
    else:
        break

💡 Counting stops early when citations drop below mid, improving efficiency.

compare

Compare count (3) with mid (2)

Since count = 3 is greater than or equal to mid = 2, we try a higher h-index by setting low = mid + 1 = 3.

💡 If enough papers have at least mid citations, we can try a larger h-index.

Line:

if count >= mid:
    low = mid + 1

💡 This step narrows the search space to higher h values.

compare

Calculate new mid = (low + high) // 2

Calculate mid = (3 + 5) // 2 = 4. This is the next candidate h-index to test.

💡 Midpoint recalculates to test the new search range.

Line:

mid = (low + high) // 2

💡 Mid updates to test a higher h-index candidate.

compare

Count papers with citations >= mid (4)

Count papers with citations >= 4 by scanning from the start: 6 and 5 qualify, 3 does not, so count = 2.

💡 Counting again tests if h = 4 is achievable.

Line:

count = 0
for c in citations:
    if c >= mid:
        count += 1
    else:
        break

💡 Early break improves efficiency once citations drop below mid.

compare

Compare count (2) with mid (4)

Since count = 2 is less than mid = 4, we try a lower h-index by setting high = mid - 1 = 3.

💡 If not enough papers meet the threshold, we reduce the search space.

Line:

else:
    high = mid - 1

💡 This step narrows the search space to smaller h values.

compare

Calculate new mid = (low + high) // 2

Calculate mid = (3 + 3) // 2 = 3. This is the next candidate h-index to test.

💡 Midpoint recalculates to test the new narrowed search range.

Line:

mid = (low + high) // 2

💡 Mid updates to test h = 3.

compare

Count papers with citations >= mid (3)

Count papers with citations >= 3: 6, 5, and 3 qualify, so count = 3.

💡 Counting confirms if h = 3 is valid.

Line:

count = 0
for c in citations:
    if c >= mid:
        count += 1
    else:
        break

💡 Exactly 3 papers have at least 3 citations.

compare

Compare count (3) with mid (3)

Since count = 3 is equal to mid = 3, we try a higher h-index by setting low = mid + 1 = 4.

💡 Equal count means h = 3 is valid, so we try for a higher h.

Line:

if count >= mid:
    low = mid + 1

💡 Search space moves up to find possibly larger h-index.

compare

Check loop condition low <= high

Now low = 4 and high = 3, so low > high. The binary search loop ends.

💡 When low passes high, the search space is exhausted and the answer is found.

Line:

while low <= high:

💡 The maximum valid h-index is high = 3.

reconstruct

Return the final h-index

Return high = 3 as the maximum h-index where at least 3 papers have 3 or more citations.

💡 The binary search result is the final answer to the problem.

Line:

return high

💡 The h-index is 3 for this input.

def hIndex(citations):  # STEP 1-2
    citations.sort(reverse=True)  # STEP 2
    n = len(citations)  # STEP 3
    low, high = 0, n  # STEP 3
    while low <= high:  # STEP 13
        mid = (low + high) // 2  # STEP 4,7,10
        count = 0  # STEP 5,8,11
        for c in citations:  # STEP 5,8,11
            if c >= mid:  # STEP 5,8,11
                count += 1  # STEP 5,8,11
            else:  # STEP 5,8,11
                break  # STEP 5,8,11
        if count >= mid:  # STEP 6,12
            low = mid + 1  # STEP 6,12
        else:  # STEP 9
            high = mid - 1  # STEP 9
    return high  # STEP 14

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

📊

H-Index (Sort + Binary Search) - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how sorting enables efficient binary search and how the h-index is found by narrowing down the search space.

none

3

0

0

1

6

2

1

3

5

4

sort

6

0

5

1

3

2

1

3

0

4

initialize_bounds

low

6

0

5

1

3

2

1

3

0

4

calculate_mid

low

6

0

5

1

mid

3

2

1

3

0

4

count

i

6

0

5

1

mid

3

2

1

3

0

4

Result: 3

move_low_up

6

0

5

1

mid

3

2

low

1

3

0

4

Result: 3

calculate_mid

6

0

5

1

3

2

low

1

3

mid

0

4

Result: 3

count

i

6

0

5

1

3

2

1

3

mid

0

4

Result: 2

move_high_down

6

0

5

1

3

2

high

1

3

mid

0

4

Result: 2

calculate_mid

6

0

5

1

3

2

mid

1

3

0

4

Result: 2

count

i

6

0

5

1

3

2

mid

1

3

0

4

Result: 3

move_low_up

6

0

5

1

3

2

mid

1

3

low

0

4

Result: 3

loop_end

6

0

5

1

3

2

high

1

3

low

0

4

Result: 3

return

6

0

5

1

3

2

high

1

3

0

4

Result: 3

Key Takeaways

✓ Sorting the citations array in descending order is essential to enable efficient binary search.

Without sorting, counting papers with citations >= mid would be inefficient and binary search wouldn't apply.

✓ Binary search narrows down the possible h-index values by testing midpoints and counting qualifying papers.

This visualizes how the search space shrinks step-by-step, which is hard to grasp from code alone.

✓ The count comparison with mid determines whether to try higher or lower h values, guiding the binary search decisions.

Seeing the count and mid comparison at each step clarifies why pointers move as they do.

Practice

1. You are given a list of non-negative integers and need to arrange them such that they form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort the numbers as strings using a custom comparator that compares concatenations.

B. Use a greedy approach that always picks the largest number first.

C. Generate all permutations of the numbers and select the maximum concatenation.

D. Apply dynamic programming to build the largest number from subproblems.

Solution

1. Step 1: Understand problem constraints

   The problem requires ordering numbers to maximize concatenated value, which is not solved by simple numeric or lexicographic sorting.

2. Step 2: Identify correct approach

   Sorting with a custom comparator comparing concatenations (a+b vs b+a) ensures correct relative order for maximum combined number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Custom comparator sorting is the standard optimal approach [OK]

Hint: Largest number needs custom string concatenation sort [OK]

Common Mistakes:

• Assuming numeric sort or lexicographic sort suffices

2. Consider the following Python function to find the minimum absolute difference in an array. What is the returned value when the input is [4, 2, 1, 3]?

def minimum_abs_difference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff == 1:
            return 1
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(minimum_abs_difference([4, 2, 1, 3]))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 2, 3, 4].

2. Step 2: Iterate and check adjacent differences

   Differences: 2-1=1 -> triggers early return 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early exit on diff==1 returns 1 [OK]

Hint: Early exit returns 1 on first adjacent difference of 1 [OK]

Common Mistakes:

• Forgetting early exit
• Returning difference between non-adjacent pairs

3. What is the time complexity of the optimal solution that sorts the list of numbers using a custom comparator comparing concatenations of strings, where n is the number of elements and k is the maximum number of digits in any number?

medium

A. O(n * k * log n) because each comparison takes O(k) and there are O(n log n) comparisons.

B. O(n^2 * k) because each comparison concatenates strings and sorting requires O(n^2) comparisons.

C. O(n log n * k) because sorting is O(n log n) and each comparison takes O(k) time.

D. O(n * k^2) because string concatenation takes O(k^2) and sorting is O(n).

Solution

1. Step 1: Identify sorting complexity

   Sorting n elements requires O(n log n) comparisons.

2. Step 2: Analyze comparison cost

   Each comparison concatenates two strings of length up to k, which takes O(k) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n log n * k) [OK]

Hint: Sorting with custom comparator costs O(n log n * k) [OK]

Common Mistakes:

• Assuming O(n^2 * k) due to misunderstanding sorting complexity

4. What is the time complexity of the optimal heap-based solution to rearrange an array so that no two adjacent elements are the same, where n is the length of the array and k is the number of unique elements?

medium

A. O(n log k) because each element is pushed and popped at most once from a heap of size k

B. O(n) because each element is processed once without heap overhead

C. O(k log n) since heap operations depend on n but only k unique elements

D. O(n²) due to repeated heap operations for each element

Solution

1. Step 1: Analyze heap operations per element

   Each element is pushed and popped at most once; heap size is at most k (unique elements).

2. Step 2: Calculate complexity based on heap operations

   Each push/pop is O(log k), total O(n log k) for n elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap operations dominate, confirming O(n log k) [OK]

Hint: Heap ops per element cost O(log k) [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Ignoring heap size dependence on k

5. Suppose the input array can contain duplicate elements and negative numbers. Which modification to the optimal approach ensures correct minimum absolute difference calculation?

hard

A. Sort the array and scan adjacent pairs, but use absolute difference instead of subtraction.

B. Sort the array and scan adjacent pairs using subtraction as is, since sorting orders negatives correctly.

C. Use nested loops to compare all pairs because sorting fails with negatives.

D. Ignore duplicates and negatives since they don't affect minimum difference.

Solution

1. Step 1: Understand sorting with negatives

   Sorting places negative numbers in ascending order correctly.

2. Step 2: Adjacent subtraction works for minimum difference

   Difference between adjacent sorted elements is always non-negative or zero; no need for absolute value.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting handles negatives; subtraction suffices [OK]

Hint: Sorting handles negatives; no abs needed on adjacent pairs [OK]

Common Mistakes:

• Using abs unnecessarily
• Thinking sorting fails with negatives