Skip to content

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;
}

Comments