274. H-Index

Given an array where citations[i] is the number of citations a researcher received for their $i^{th}$ paper, calcuate the researcher's h-index.

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.

Intuition

• H-index is x if researcher has published at least x papers with at least x citation.

• The maximum H-index will be the amount of papers published

  • Any paper having citation more than the amount of papers published is useless

• Start from the maximum citation and move towards 0

  • If amount of papers having citation x is greater or equal to x it the h-index

Approach

• Store amount of paper with citation $i$ in an array

  • the array needs to be of length equal to number of paper published

• If a paper has citation greater than number of papers published add it to the max citation value.

• Iterate from end and for citation $i$ sum the paper with citation $\geq i$ if its greater than $i$ return as thats the h-index.

Complexity

• Time complexity : $\text{O}(n)$

  • We iterate the array only once

• Space complexity : $\text{O}(n)$

  • We use space to store the papers with citation $i$.

Code

public int hIndex(int[] citations) {
	// use extra space as single paper with x citation will mean score of 1
	int[] countOfPapers = new int[citations.length + 1];
	
	for (int i = 0; i < citations.length; ++i) {
		if (citations[i] > citations.length) {
			countOfPapers[citations.length]++;
		} else {
			countOfPapers[citations[i]]++;
		}
	}
	
	int papersTillNow = 0;
	for (int i = citations.length; i >= 0; --i) {
		papersTillNow += countOfPapers[i];
		if (papersTillNow >= i) return i;
	}
	
	
	return 0;
}