Leetcode 275. H-Index II

Problem Explanation

The problem requires us to calculate a researcher's h-index given their citations history, sorted in ascending order. The h-index is a metric that measures both the productivity and the impact of a researcher. The definition of h-index is that a scholar has an h-index if h of their n articles have at least h citations each, and the rest articles have no more than h citations each.

The problem looks tricky initially but simplifies dramatically when we understand the definition of h-index properly. For instance,

1
2plaintext
3Input : [0,1,3,5,6]
4Output : 3

In above example, if we go by the definition, the researcher has 3 papers with 3 or more citations and the remaining papers have no more than 3 citations. Therefore, the h-index for the researcher is 3.

Approach

The citations are already sorted, so instead of finding out the cut-off point for h-index papers, we can bisect the array until we find the h-index. The cut-off point for the h-index would be at the position when citations[m] >= n - m, where m is the mid-point index, and n - m is the count of papers on the right side (those with more citations). We are looking for the first position that meets the above condition from the right hand side and return n - l as the h-index.

Python Solution

1
2python
3class Solution:
4    def hIndex(self, citations):
5        n = len(citations)
6        l, r = 0, n
7        while l < r:
8            m = (l + r) // 2
9            if citations[m] >= n - m:
10                r = m
11            else:
12                l = m + 1
13
14        return n - l

Java Solution

1
2java
3public class Solution {
4    public int hIndex(int[] citations) {
5        int n = citations.length;
6        int l = 0, r = n;
7        while (l < r) {
8            int m = (l + r) / 2;
9            if (citations[m] >= n - m) {
10                r = m;
11            } else {
12                l = m + 1;
13            }
14        }
15        return n - l;
16    }
17}

JavaScript Solution

1
2javascript
3var Solution = function() { };
4
5Solution.prototype.hIndex = function(citations) {
6    var n = citations.length;
7    var l = 0, r = n;
8    while (l < r) {
9        var m = Math.floor((l + r) / 2);
10        if (citations[m] >= n - m) {
11            r = m;
12        } else {
13            l = m + 1;
14        }
15    }
16    return n - l;
17};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int hIndex(vector<int>& citations) {
6        int n = citations.size();
7        int l = 0, r = n;
8        while (l < r) {
9            int m = (l + r) / 2;
10            if (citations[m] >= n - m) {
11                r = m;
12            } else {
13                l = m + 1;
14            }
15        }
16        return n - l;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int HIndex(int[] citations) {
5        int n = citations.Length;
6        int l = 0, r = n;
7        while (l < r) {
8            int m = (l + r) / 2;
9            if (citations[m] >= n - m) {
10                r = m;
11            } else {
12                l = m + 1;
13            }
14        }
15        return n - l;
16    }
17}

In the given solutions we perform a binary search manipulation on the given ordered array. The positions are moved based on the condition citations[m] >= n - m. If the current element at middle index m is greater than or equal to the count of numbers towards its right, we shift the right pointer towards middle, else we move the left pointer forward.

The time complexity of all these solutions is O(log n) as we are applying the binary search algorithm. It is important to note that the search space is halved at each step, therefore making the computation faster as the input size increases.

The space complexity of all these solutions is O(1) as they use constant additional space. These solutions are in-place, i.e. they don't use any additional memory whereas the input structures are not modified.

These solutions are efficient and will work well even with a huge number of citations because of their logarithmic time complexity. Utilizing the property that the input array is sorted in ascending order guarantees that we only need to check a subpart of the whole array, thus reducing unnecessary computation.

This problem is a lot about figuring out the appropriate property and conditions to perform your operations on. Understanding the h-index is crucial for solving this problem. It shows the power of binary search and how it can be used to solve problems that seem like they need more info than given. Prior reading about h-indexes and the significance of it in academia can be beneficial while tackling this problem.

In summary, keeping in mind the sorted nature of array and the properties of h-index, we can solve this problem efficiently. These kind of problems can show up in different scenarios such as finding a key index in logs, analyzing the significance of website hits and so on. Therefore, such algorithms are very beneficial to learn and understand. Start practicing today!