LeetCode 0274. H-Index Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, 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.

 

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 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,3,1]
Output: 1

 

Constraints:

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

Solutions

Solution 1: Sorting

We can sort the array citations in descending order. Then we enumerate the value h from large to small, if there is an h value satisfying citations[h-1] ≥ h, it means that there are at least h papers that have been cited at least h times, just return h directly. If we cannot find such an h value, it means that all the papers have not been cited, return 0.

Time complexity O(n × log n), space complexity O(log n). Here n is the length of the array citations.

PythonJavaC++GoTypeScriptRust

class Solution: def hIndex(self, citations: List[int]) -> int: citations.sort(reverse=True) for h in range(len(citations), 0, -1): if citations[h - 1] >= h: return h return 0(code-box)

class Solution { public int hIndex(int[] citations) { Arrays.sort(citations); int n = citations.length; for (int h = n; h > 0; --h) { if (citations[n - h] >= h) { return h; } } return 0; } }(code-box)

class Solution { public: int hIndex(vector<int>& citations) { sort(citations.rbegin(), citations.rend()); for (int h = citations.size(); h; --h) { if (citations[h - 1] >= h) { return h; } } return 0; } };(code-box)

func hIndex(citations []int) int { sort.Ints(citations) n := len(citations) for h := n; h > 0; h-- { if citations[n-h] >= h { return h } } return 0 }(code-box)

function hIndex(citations: number[]): number { citations.sort((a, b) => b - a); for (let h = citations.length; h; --h) { if (citations[h - 1] >= h) { return h; } } return 0; }(code-box)

impl Solution { #[allow(dead_code)] pub fn h_index(citations: Vec<i32>) -> i32 { let mut citations = citations; citations.sort_by(|&lhs, &rhs| rhs.cmp(&lhs)); let n = citations.len(); for i in (1..=n).rev() { if citations[i - 1] >= (i as i32) { return i as i32; } } 0 } }(code-box)

Solution 2: Counting + Sum

We can use an array cnt of length n+1, where cnt[i] represents the number of papers with the reference count of i. We traverse the array citations and treat the papers with the reference count greater than n as papers with a reference count of n. Then we use the reference count as the index and add 1 to the corresponding element of cnt for each paper. In this way, we have counted the number of papers for each reference count.

Then we enumerate the value h from large to small, and add the element value of cnt with the index of h to the variable s, where s represents the number of papers with a reference count greater than or equal to h. If s ≥ h, it means that at least h papers have been cited at least h times, just return h directly.

Time complexity O(n), space complexity O(n). Here n is the length of the array citations.

PythonJavaC++GoTypeScript

class Solution: def hIndex(self, citations: List[int]) -> int: n = len(citations) cnt = [0] * (n + 1) for x in citations: cnt[min(x, n)] += 1 s = 0 for h in range(n, -1, -1): s += cnt[h] if s >= h: return h(code-box)

class Solution { public int hIndex(int[] citations) { int n = citations.length; int[] cnt = new int[n + 1]; for (int x : citations) { ++cnt[Math.min(x, n)]; } for (int h = n, s = 0;; --h) { s += cnt[h]; if (s >= h) { return h; } } } }(code-box)

class Solution { public: int hIndex(vector<int>& citations) { int n = citations.size(); int cnt[n + 1]; memset(cnt, 0, sizeof(cnt)); for (int x : citations) { ++cnt[min(x, n)]; } for (int h = n, s = 0;; --h) { s += cnt[h]; if (s >= h) { return h; } } } };(code-box)

func hIndex(citations []int) int { n := len(citations) cnt := make([]int, n+1) for _, x := range citations { cnt[min(x, n)]++ } for h, s := n, 0; ; h-- { s += cnt[h] if s >= h { return h } } }(code-box)

function hIndex(citations: number[]): number { const n: number = citations.length; const cnt: number[] = new Array(n + 1).fill(0); for (const x of citations) { ++cnt[Math.min(x, n)]; } for (let h = n, s = 0; ; --h) { s += cnt[h]; if (s >= h) { return h; } } }(code-box)

Solution 3: Binary Search

We notice that if there is a h value that satisfies at least h papers are cited at least h times, then for any h'<h, at least h' papers are cited at least h' times. Therefore, we can use the binary search method to find the largest h such that at least h papers are cited at least h times.

We define the left boundary of binary search l=0 and the right boundary r=n. Each time we take mid = \lfloor ^{l + r + 1}⁄₂ \rfloor, where \lfloor x \rfloor represents floor x. Then we count the number of elements in array citations that are greater than or equal to mid, and denote it as s. If s ≥ mid, it means that at least mid papers are cited at least mid times. In this case, we change the left boundary l to mid. Otherwise, we change the right boundary r to mid-1. When the left boundary l is equal to the right boundary r, we find the largest h value, which is l or r.

Time complexity O(n × log n), where n is the length of array citations. Space complexity O(1).

PythonJavaC++GoTypeScript

class Solution: def hIndex(self, citations: List[int]) -> int: l, r = 0, len(citations) while l < r: mid = (l + r + 1) >> 1 if sum(x >= mid for x in citations) >= mid: l = mid else: r = mid - 1 return l(code-box)

class Solution { public int hIndex(int[] citations) { int l = 0, r = citations.length; while (l < r) { int mid = (l + r + 1) >> 1; int s = 0; for (int x : citations) { if (x >= mid) { ++s; } } if (s >= mid) { l = mid; } else { r = mid - 1; } } return l; } }(code-box)

class Solution { public: int hIndex(vector<int>& citations) { int l = 0, r = citations.size(); while (l < r) { int mid = (l + r + 1) >> 1; int s = 0; for (int x : citations) { if (x >= mid) { ++s; } } if (s >= mid) { l = mid; } else { r = mid - 1; } } return l; } };(code-box)

func hIndex(citations []int) int { l, r := 0, len(citations) for l < r { mid := (l + r + 1) >> 1 s := 0 for _, x := range citations { if x >= mid { s++ } } if s >= mid { l = mid } else { r = mid - 1 } } return l }(code-box)

function hIndex(citations: number[]): number { let l = 0; let r = citations.length; while (l < r) { const mid = (l + r + 1) >> 1; let s = 0; for (const x of citations) { if (x >= mid) { ++s; } } if (s >= mid) { l = mid; } else { r = mid - 1; } } return l; }(code-box)