274. H-Index

 

Efficient Solution for H-Index II Using Binary Search

In this post, we will discuss an efficient solution for the H-Index II problem using binary search.

Problem Statement

The H-Index is a metric used to measure the productivity and impact of a researcher's publications. Given an array of integers citations[] where each integer represents the number of citations a paper has received, the task is to find the researcher's H-Index.

A scientist has an H-Index if h of their papers have at least h citations each, and the remaining papers have no more than h citations.

In this variation of the problem (H-Index II), the citations[] array is sorted in ascending order.

Approach

Given that the array is already sorted, we can leverage binary search to find the H-Index efficiently. Binary search reduces the time complexity to O(log n), making it ideal for large datasets.

Key Observation

For a sorted array citations[], if we are at index mid, then the number of papers that have at least citations[mid] citations is size - mid (where size is the length of the array).

We are looking for the largest h such that:

  • citations[mid] >= size - mid
  • In other words, the number of papers that have at least citations[mid] citations is greater than or equal to citations[mid].

Solution Explanation

Here is the JavaScript code that implements the binary search solution:

javascript
var hIndex = function(citations) {
    // Get the size of the array
    var size = citations.length;
    
    // Initialize the low and high pointers for binary search
    let low = 0;
    let high = size - 1;
    
    // Variable to store the maximum h-index found
    var h = 0;
    
    // Binary search loop
    while (low <= high) {
        // Find the mid-point of the current range
        var mid = Math.floor((low + high) / 2);
        
        // Check if the number of papers with at least citations[mid] is enough
        if (citations[mid] >= size - mid) {
            // If yes, update h to the current number of papers
            h = size - mid;
            // Move to the left part to find a higher h-index
            high = mid - 1;
        } else {
            // Otherwise, move to the right part
            low = mid + 1;
        }
    }
    
    // Return the found h-index
    return h;
};


java

class Solution {
    public int hIndex(int[] citations) {
        // binary search apply
    int size = citations.length;
    int low  = 0;
    int high = size - 1;
    int h = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if(citations[mid] >= size - mid) {
            h = size - mid;
            high = mid - 1;
        }else {
            low = mid + 1;
        }
    }
    return h;
}
}

Step-by-Step Explanation

  1. Initialization:

    • We initialize the low pointer at 0 (beginning of the array) and the high pointer at size - 1 (end of the array).
    • h is used to track the maximum H-Index we find during the binary search.

  2. Binary Search Loop:

    • At each step, we calculate the mid index as the average of low and high.
    • We check if citations[mid] >= size - mid. This checks if the number of papers with at least citations[mid] citations is greater than or equal to citations[mid] itself. If this condition holds, it means the current mid-point can be a candidate for the H-Index.
    • If the condition is true, we update h to size - mid and move the high pointer to mid - 1 to check for higher possible H-Index values.
    • If the condition is false, it means we need to look to the right of the current mid-point, so we move the low pointer to mid + 1.

  3. Return the H-Index:

    • The loop runs until low exceeds high, and we return the maximum H-Index found during the binary search.

Time Complexity

The time complexity of this algorithm is O(log n), thanks to the binary search approach. This is much faster than the brute force method, which would require linear time O(n) to check each element.

Space Complexity

The space complexity is O(1), as we are only using a constant amount of extra space.

Conclusion

This binary search-based solution is a highly efficient way to solve the H-Index II problem, especially for large arrays of citation counts. By exploiting the sorted nature of the input array, we reduce the problem to a logarithmic time complexity solution.

Feel free to use this approach to solve the H-Index II problem on LeetCode or any similar coding platform!

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more