Dare2Solve
The h-index is a metric that measures both the productivity and citation impact of a researcher's publications. The h-index is defined as the maximum value of h
such that the given author has published at least h
papers that have each been cited at least h
times.
Given an array citations
where citations[i]
is the number of citations a researcher received for their i-th
paper, calculate the researcher's h-index.
The h-index represents the highest number of papers h
that have at least h
citations. The problem can be visualized by counting how many papers have each possible citation count. If we aggregate these counts, starting from the highest possible citation count, we can determine the largest h
where at least h
papers have h
or more citations.
Count Citations:
counts
of size maxCitation + 1
to store how many papers have each specific citation count.Aggregate Paper Counts:
counts
array with the number of papers for each citation count.Determine h-Index:
h
. If so, that h
is the h-index.Edge Case:
h
is found, return 0
, though by definition, the h-index should be at least 0.O(n)
, where n
is the length of the citation array. We make a single pass to count the citations and another pass to determine the h-index.O(m)
, where m
is the maximum citation count in the array. This space is used for the counts
array to store the number of papers with each possible citation count.class Solution {
public:
int hIndex(std::vector<int>& citations) {
int maxCitation = *std::max_element(citations.begin(), citations.end());
std::vector<int> counts(maxCitation + 1, 0);
// Step 1: Count the number of papers for each citation count
for (int citation : citations) {
counts[citation]++;
}
int totalPapers = 0;
// Step 2: Calculate how many papers have at least `h` citations
for (int h = maxCitation; h >= 0; h--) {
totalPapers += counts[h];
if (totalPapers >= h) {
return h;
}
}
return 0; // Fallback
}
};
class Solution:
def hIndex(self, citations: List[int]) -> int:
max_citation = max(citations)
counts = [0] * (max_citation + 1)
# Step 1: Count the number of papers for each citation count
for citation in citations:
counts[citation] += 1
total_papers = 0
# Step 2: Calculate how many papers have at least `h` citations
for h in range(max_citation, -1, -1):
total_papers += counts[h]
if total_papers >= h:
return h
return 0 # Fallback
class Solution {
public int hIndex(int[] citations) {
int maxCitation = Arrays.stream(citations).max().getAsInt();
int[] counts = new int[maxCitation + 1];
// Step 1: Count the number of papers for each citation count
for (int citation : citations) {
counts[citation]++;
}
int totalPapers = 0;
// Step 2: Calculate how many papers have at least `h` citations
for (int h = maxCitation; h >= 0; h--) {
totalPapers += counts[h];
if (totalPapers >= h) {
return h;
}
}
return 0; // Fallback
}
}
function hIndex(citations) {
const maxCitation = Math.max(...citations);
const counts = new Array(maxCitation + 1).fill(0);
// Step 1: Count the number of papers for each citation count
for (let citation of citations) {
counts[citation]++;
}
let totalPapers = 0;
// Step 2: Calculate how many papers have at least `h` citations
for (let h = maxCitation; h >= 0; h--) {
totalPapers += counts[h];
if (totalPapers >= h) {
return h;
}
}
return 0; // Fallback, though h-index should be at least 0
}