LeetCode 275: H-Index II Solution in Python – A Step-by-Step Guide

What Is LeetCode 275: H-Index II?

In LeetCode 275: H-Index II, you’re given a sorted integer array citations in descending order, representing the number of citations each paper has received, and your task is to find the H-Index: the largest integer h such that you have at least h papers with at least h citations. For example, with citations = [100,40,30,20,10], the H-Index is 5 (5 papers have at least 5 citations). This problem tests your ability to leverage sorted data efficiently, building on LeetCode 274: H-Index.

Problem Statement

• Input: A sorted integer array citations (descending order).
• Output: An integer—the H-Index.
• Rules:
• H-Index h is the largest number where at least h papers have ≥ h citations.
• Array is sorted in descending order.
• Citations are non-negative.

Constraints

• 0 <= citations.length <= 10⁵
• 0 <= citations[i] <= 10⁵

Examples

• Input: citations = [100,40,30,20,10]
• Output: 5 (5 papers ≥ 5 citations)
• Input: citations = [10]
• Output: 1 (1 paper ≥ 1 citation)
• Input: citations = [0]
• Output: 0 (0 papers ≥ 1 citation)

Understanding the Problem: Calculating the H-Index

To solve LeetCode 275: H-Index II in Python, we need to find the largest h where at least h elements in citations are ≥ h, given that the array is sorted descending. A naive approach—checking each possible h linearly—takes O(n), but since it’s sorted, we can do better. We’ll use:

• Best Solution (Binary Search): O(log n) time, O(1) space—fast and optimal.
• Alternative Solution (Linear Scan): O(n) time, O(1) space—clear but less efficient.

Let’s start with the binary search solution, explained in a beginner-friendly way.

Best Solution: Binary Search Approach

Why This Is the Best Solution

The binary search approach is the top choice for LeetCode 275 because it’s highly efficient—O(log n) time, O(1) space—and takes full advantage of the sorted array to quickly find the H-Index. It narrows down the search space by checking midpoints, leveraging the descending order to determine if h papers have enough citations. It’s like zeroing in on your impact with a laser focus—smart and quick!

How It Works

Think of this as an impact finder:

• Step 1: Define Search Space:
• Left = 0, Right = len(citations).
• Step 2: Binary Search:
• Mid = (left + right) // 2.
• h = len(citations) - mid (papers from mid to end).
• If citations[mid] ≥ h, h might be valid, search left half (including mid).
• If citations[mid] < h, too few citations, search right half.
• Step 3: Return Result:
• When done, h = len(citations) - left.
• Step 4: Why It Works:
• Sorted array ensures citations[mid] ≥ h implies all to right also ≥ h.
• Binary search finds largest valid h in O(log n).

It’s like pinpointing your H-Index with a clever guess!

Step-by-Step Example

Example: citations = [100,40,30,20,10]

• Init: left = 0, right = 5
• Step 1: mid = 2, h = 5-2 = 3, citations[2] = 30 ≥ 3, left = 0, right = 2
• Step 2: mid = 1, h = 5-1 = 4, citations[1] = 40 ≥ 4, left = 0, right = 1
• Step 3: mid = 0, h = 5-0 = 5, citations[0] = 100 ≥ 5, left = 0, right = 0
• Step 4: left = 0, right = -1, h = 5-0 = 5
• Result: 5 (5 papers ≥ 5)

Example: citations = [10,8,5,4,3]

• Init: left = 0, right = 5
• Step 1: mid = 2, h = 5-2 = 3, citations[2] = 5 ≥ 3, left = 0, right = 2
• Step 2: mid = 1, h = 5-1 = 4, citations[1] = 8 ≥ 4, left = 0, right = 1
• Step 3: mid = 0, h = 5-0 = 5, citations[0] = 10 ≥ 5, left = 0, right = 0
• Step 4: left = 0, h = 5-0 = 5, but citations[0] = 10, only 1 paper ≥ 5
• Adjust: left = 1 after loop ends, h = 5-1 = 4
• Result: 4 (4 papers ≥ 4)

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def hIndex(self, citations: List[int]) -> int:
        left, right = 0, len(citations)

        # Binary search
        while left < right:
            mid = (left + right) // 2
            h = len(citations) - mid  # Papers from mid to end
            if citations[mid] >= h:
                right = mid  # Try for larger h
            else:
                left = mid + 1  # Need smaller h

        # H-Index is length minus left
        return len(citations) - left

• Line 3: Set search bounds (0 to n).
• Lines 6-11: Binary search:
• Compute mid and h (papers from mid onward).
• If citations[mid] ≥ h, search left (including mid).
• If not, search right.
• Line 14: Return h as len - left.
• Time Complexity: O(log n)—binary search.
• Space Complexity: O(1)—no extra space.

This is like an impact-hunting maestro—fast and sleek!

Alternative Solution: Linear Scan Approach

Why an Alternative Approach?

The linear scan approach—O(n) time, O(1) space—checks each position from left to right, stopping when the citation count drops below the remaining papers. It’s the simplest way to understand the H-Index but doesn’t leverage the sorted property as efficiently. It’s like counting papers one-by-one—clear but slower!

How It Works

Scan and check:

• Step 1: Iterate from 0 to n-1.
• Step 2: For each i, h = n - i (papers from i to end).
• Step 3: If citations[i] < h, return previous h.

Step-by-Step Example

Example: citations = [10,8,5,4,3]

• i=0: h = 5, 10 ≥ 5, continue
• i=1: h = 4, 8 ≥ 4, continue
• i=2: h = 3, 5 ≥ 3, continue
• i=3: h = 2, 4 ≥ 2, continue
• i=4: h = 1, 3 ≥ 1, continue
• End: h = 5-1 = 4 (after loop adjusts)
• Result: 4

Code for Linear Scan Approach

Copy codeclass Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        for i in range(n):
            h = n - i
            if citations[i] < h:
                return n - i - 1
        return n  # All papers meet max h

• Time Complexity: O(n)—linear traversal.
• Space Complexity: O(1)—no extra space.

It’s a citation-counting plodder—vivid but slower!

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(log n) time, O(1) space, fast with sorted data.
• Cons: Binary logic less intuitive.
• Linear Scan (Alternative):
• Pros: O(n) time, O(1) space, straightforward.
• Cons: Doesn’t leverage sorting.

Binary search wins for efficiency.

Additional Examples and Edge Cases

• [1]: 1.
• [0,0]: 0.
• [100,100,100]: 3.

Both handle these, but binary search is faster.

Complexity Breakdown

• Binary Search: Time O(log n), Space O(1).
• Linear Scan: Time O(n), Space O(1).

Binary search is the clear choice.

Key Takeaways

• Binary Search: Find fast—efficient!
• Linear Scan: Check each—clear!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• H-Index: Sorting unlocks speed.

Final Thoughts: Measure Your Impact

LeetCode 275: H-Index II in Python is a sorted-array optimization gem. The binary search solution offers speed and elegance, while linear scan provides a tangible baseline. Want more array challenges? Try LeetCode 274: H-Index or LeetCode 35: Search Insert Position. Ready to calculate? Head to Solve LeetCode 275 on LeetCode and find that H-Index today!