H-Index II in C++

The H-Index II problem in C++ is a variation of the classic H-Index problem, specifically designed to work with a sorted array. The H-Index is a metric used to measure the productivity and citation impact of a researcher, where the goal is to find the largest number h such that the researcher has at least h papers with at least h citations.

Problem Overview:

Given a sorted array of citations[] of non-negative integers, where each element represents the number of citations a researcher's paper has received, the task is to determine the researcher's H-Index. The array is sorted in ascending order, and you need to find the maximum value of h such that there are at least h papers with at least h citations.

Approach 1: Simple Approach

Output:

 
The H-Index is: 3   

Explanation:

Step 1: Input and Initialization

• The problem gives us a sorted list of integers, where each integer represents the number of citations a paper has received. The length of the list, n, tells us how many papers there are in total. Our goal is to find the highest value of h such that at least h papers have received h or more citations.
• We start by setting up two pointers: low and high. The low pointer is set at the beginning of the list (index 0), and the high pointer is set at the end of the list (index n-1). These pointers define the range where we'll search for the correct h value.

Step 2: Binary Search Loop

• Now, we use a binary search to efficiently narrow down where the H-Index could be. We compute the mid-point in the list, called mid, by taking the average of low and high. This gives us a paper at position mid, and the number of citations that paper has.
• For every paper at position mid, we also calculate how many papers have citations greater than or equal to the citations of the mid paper. This is done by computing n - mid, which tells us how many papers come after mid (including mid itself).

Step 3: Condition Checking

• After calculating the number of papers that meet the citation threshold, we check whether it matches the number of citations of the paper at mid. This forms the crux of the solution:
• If the number of documents n - mid equals the citation count of the paper at mid, we have found the H-Index. This is because the number of documents with at least h citations is precisely equal to the citation count, satisfying the definition of H-Index.
• If the number of papers with sufficient citations is less than the citation count, it means we need to search the left side of the list. In this case, we move the high pointer to the left to narrow the search.
• If the number of papers with sufficient citations is greater than the citation count, it means we need to look at the right side of the list. Therefore, we move the low pointer to the right, expanding our search in that direction.

Step 4: Search Completion

• The binary search continues, narrowing down the search range by adjusting low and high based on the comparisons until the pointers converge and the search terminates. If no exact match is found during the search, the final result is determined by the number of papers that would meet the h-index condition at the last position of the low pointer.

Step 5: Return the H-Index

• At the end of the binary search, the H-Index is computed based on where the search converged. Specifically, the value n - low gives the maximum number of papers with at least that many citations, and this represents the H-Index.

Time Complexity:

• Binary Search: At each step, the search space is halved, meaning that instead of scanning all n elements in the list, the algorithm performs approximately log n steps (where n is the number of papers).
• Since in each step, we only compare the mid-point element with its corresponding citation value, the total time complexity is O(log n).

Space Complexity:

• The algorithm only uses a constant amount of extra space for variables such as low, high, mid, and a few other temporary values. No additional data structures (like arrays or lists) are used.
• Therefore, the space complexity is O(1), or constant space, meaning it doesn't grow with the size of the input.

Approach 2: Using Linear Scan Approach

Since the array is already sorted, one simple approach is to scan through the array in a single pass and calculate the H-Index directly. This approach sacrifices efficiency for simplicity, as it avoids the complexity of binary search.

Output:

 
The H-Index is: 3   

Explanation:

Understanding the Input:

• You are given a list of citations for each paper, sorted in ascending order. This means that the documents with fewer citations are listed before those with more citations.

Traversal Strategy:

• The approach involves scanning through the list from the beginning to the end. As you scan, you'll determine how many papers have at least a certain number of citations. The goal is to find the highest number h that satisfies the condition of having at least h papers with at least h citations.

Calculate the Number of Papers with Sufficient Citations:

• For each position in the list, consider the citation value at that position. This citation value indicates the minimum number of citations required for papers to be considered.
• Calculate the number of papers that have at least this number of citations. Since the list is sorted, this is simply the total number of documents minus the current index. For example, if you are at index i, then there are n - i papers from index i to the end of the list (including the paper at index i itself).

Check the Condition:

• Compare the current citation value with the calculated number of documents having at least that many citations.
• If the citation value at the current index is greater than or equal to the number of papers that need to have at least that many citations, then this citation value could be a valid H-Index. Return this value as a result .

Continue Scanning:

• If the condition is not met, move to the following index and repeat the process. Continue this until you find a valid H-Index or finish scanning the list.

Handle Edge Cases:

• If the list is entirely scanned without finding a valid H-Index, it means no such h exists where the number of papers with h citations is sufficient. In this case, return 0 as the H-Index.

Complexity analysis:

Time Complexity:

O(n): In the Linear Scan Approach, you traverse the entire list of citations only once. Each step involves simple arithmetic operations and comparisons, so the time complexity is linear with respect to the number of citations.

Space Complexity:

O(1): The approach uses a constant amount of extra space. You only need a few variables to keep track of the current index and the result. No additional data structures or memory allocations are required beyond this.

Approach 3: Using Counting Sort-Based Approach

This approach is similar to a counting sort, where you count how many papers have a specific number of citations, then accumulate these counts to find the H-Index. This method works well if citation values are not too large

Implementation:

Output:

 
The H-Index is: 3   

Explanation:

Input and Initialization:

• You're given a sorted or unsorted list of citation counts for several papers. Let's assume the total number of documents is n.
• You need to create a counting array (count array) where each index represents how many papers have a specific number of citations. This array will help track how often each citation value appears.

Counting Citation Occurrences:

• In the list of citations, for each citation, increase the value in the count array at the position that matches the number of citations.
• If a paper has more citations than n (which means more citations than the total number of papers), you cap its count at n because having more citations than papers doesn't affect the H-Index.
• For example, if you have n papers, create a count array of size n + 1. If a paper has five citations, increment the value at index 5. If a paper has more than n citations, increment the last index (n).

Accumulating Counts from High to Low:

• Once the count array is populated, we need to figure out how many papers have at least i citations for each possible i.
• To do this, start at the largest index (i.e., the maximum possible citation count, which is n) and move downwards.
• For each index, accumulate the number of papers with that many or more citations. This helps track how many papers have at least a certain number of citations.
• As you move from high citation values to low, you're essentially adding up the number of papers that meet or exceed that citation count.

H-Index Condition:

• The goal is to find the highest i such that there are at least i papers with i or more citations. So, as you're accumulating the counts, check if the accumulated count (i.e., the number of papers with citations greater than or equal to i) is greater than or equal to i.
• As soon as this condition is satisfied, i is your H-Index.

Edge Cases:

• If no such index is found where the number of papers with i or more citations is at least i, the H-Index is 0. This would happen if none of the documents has enough citations to meet the minimum condition for an H-Index.

Complexity analysis:

Time Complexity:

O(n): The Counting Sort-Based Approach traverses the citation list once to populate the count array and then traverses the count array once to compute the H-Index.

Populating the count array takes O(n) time, where n is the number of papers.

Accumulating the counts to determine the H-Index also takes O(n) time since the size of the count array is n + 1.

Thus, the total time complexity is O(n).

Space Complexity:

O(n): The space complexity is dominated by the count array, which is of size n + 1, where n is the number of papers. Since no additional data structures are used, the space complexity remains linear in terms of the number of documents.