Leetcode Daily - H-Index

Leetcode Daily - August 11, 2020

H-index

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

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, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Check Possible H-Index Values

(Submission - Accepted)

To start out this question, I decided to think about how I would solve this for simple arrays as a human. I took a minute to understand and clarify the definition of h-index.

"A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

I made the following notes:

• The h-index is a type of maximum value which satisfies the stated conditions.
• The h-index depends on counting the number of papers which satisfies a condition.
• The condition is simply related to the number in the array (number of citations).

I decided that for my first attempt I could complete it with an O(n²) solution. First we set the h-index to be the maximum possible value, which is the number of papers published. Then we iterate down and check if it meets the h-index conditions.

Submitted Code:

var hIndex = function(citations) {
    let tryH = citations.length;

    while (tryH > 0) {
        let counter = 0;
        for (let i = 0; i < citations.length; i++) {
            if (citations[i] >= tryH) counter ++;
        }
        if (counter >= tryH) return tryH;
        tryH --
    }
    return 0;
};

Attempt 2 - Remove one iterative loop from O(n²) solution

(Submission - Accepted)

I have to admit here that while I realized I needed to optimize on the O(n²) solution, I also realized that I had seen this problem before.

I had seen this problem in the introduction section of the book: Elements of Programming Interviews in Python, where they detail the thought process and more optimal solution to the h-index problem.

I use the same concept they explain in the book, which is to sort the array first. This is because, if you sort the array from high to low, then if citations[i] >= i+1 then all the previous values in citations are also greater than or equal to i+1, which is the number of papers (array index but counting starting from 1 instead of 0).

Assuming the sort is O(nlog(n)), now the iterative element of the algorithm is O(n) so the total time complexity is O(nlog(n)).

Submitted Code:

var hIndex = function(citations) {
    citations.sort((a,b) => b-a);

    let counter = 0;

    for (let i = 0; i < citations.length; i++) {
        if (citations[i] >= i+1) counter++;
        else return counter;
    }

    return counter;
};

Discussion and Conclusions

This is a very interesting example for me because it touches on a lot of challenges newer coders might run into on technical interview questions. The first one is to clarify and understand the question correctly. The second is to understand the approach and how to optimize it. And finally, it is personally interesting to me because I got the Elements of Programming Interviews book when I started studying coding challenges, and it took me a long time to comprehend and try programming the questions. But after almost one year of studying I feel so much more comfortable with questions like these that I want to remember what my initial feeling of being challenged was like so I won't be as intimidated by harder questions in the future.