Description
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
You must write an algorithm that runs in logarithmic time.
Examples:
Example 1:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,2,100]
Output: 2Solution in Python
To solve this problem in logarithmic time, we can leverage binary search since the array of citations is sorted in ascending order. The h-index is the maximum value h such that the researcher has published at least h papers, each with at least h citations.
We want to find the point in the sorted array where the number of papers with citations greater than or equal to a particular value equals that value. Since the array is sorted, we can use binary search to efficiently find this point.
Approach:
- Binary Search Setup:
- We will apply binary search over the range of indices in the citations list.
- For each midpoint
mid, check if the number of papers with citations greater than or equal tocitations[mid]is at leastcitations[mid].
- Conditions to Check:
- If
citations[mid]is greater than or equal to the number of papers frommidto the end of the list (i.e.,n - mid), then we have a potential h-index. - We continue searching in the left or right half depending on whether this condition holds, narrowing down the range.
- If
- Edge Cases:
- If all papers have low citations, the h-index might be 0.
- If all papers have high citations, the h-index will be the number of papers.
Python
from typing import List
class Solution:
def hIndex(self, citations: List[int]) -> int:
n = len(citations) # Number of papers
left, right = 0, n - 1 # Binary search range
while left <= right:
mid = left + (right - left) // 2 # Find the middle index
# Check how many papers have citations >= citations[mid]
if citations[mid] >= n - mid:
# If true, this is a potential h-index, but there might be a larger one
right = mid - 1
else:
# Otherwise, look for a higher h-index in the right half
left = mid + 1
# The final result will be the number of papers - left, which gives the maximum h-index
return n - leftExplanation of the Code:
leftandrightpointers:leftstarts at 0 (the first paper), andrightstarts atn-1(the last paper).
- Binary search loop:
- We compute
midas the middle point betweenleftandright. - We check if the number of papers from
midto the end (which isn - mid) is greater than or equal tocitations[mid]. If this condition holds, we reduce the search range by adjustingrightto search for potentially larger h-index values. - If the condition doesn’t hold, we adjust
leftto look in the right half of the array.
- We compute
- Return statement:
- After the loop,
leftwill point to the first index where the condition fails. The number of papers fromleftto the end of the list is the maximum valid h-index.
- After the loop,
Solution in C++
C++
#include <vector>
using namespace std;
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(); // Get the number of papers
int left = 0, right = n - 1; // Set the search boundaries for binary search
while (left <= right) {
int mid = left + (right - left) / 2; // Calculate the middle index to avoid overflow
// Check if citations[mid] is a potential h-index
if (citations[mid] >= n - mid) {
// If true, this means citations[mid] is a valid h-index candidate
// There may be a larger valid h-index, so search the left half
right = mid - 1;
} else {
// Otherwise, continue the search in the right half
left = mid + 1;
}
}
// The final result is the number of papers - left, which gives the maximum h-index
return n - left;
}
};Solution in Javascript
JavaScript
var hIndex = function(citations) {
let n = citations.length; // Number of papers
let left = 0, right = n - 1; // Initialize binary search bounds
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2); // Calculate the middle index
// Check if the number of citations at mid is a potential h-index
if (citations[mid] >= n - mid) {
// If citations[mid] is valid, check for a larger h-index by moving to the left
right = mid - 1;
} else {
// Otherwise, check the right side for a valid h-index
left = mid + 1;
}
}
// The final result is the number of papers - left, which gives the maximum h-index
return n - left;
};Solution in Java
Java
class Solution {
public int hIndex(int[] citations) {
int n = citations.length; // Number of papers
int left = 0, right = n - 1; // Initialize binary search boundaries
// Binary search to find the h-index
while (left <= right) {
int mid = left + (right - left) / 2; // Calculate middle index
// Check if citations[mid] is a valid h-index
if (citations[mid] >= n - mid) {
// If true, check if a larger h-index can be found, so search the left side
right = mid - 1;
} else {
// Otherwise, search the right side
left = mid + 1;
}
}
// The final h-index is calculated as the number of papers minus the 'left' pointer
return n - left;
}
}