Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Goeduhub's Online Courses @ Udemy in Just INR 570/-
Online Training - Youtube Live Class Link
0 like 0 dislike
in Coding Questions by Goeduhub's Expert (2.3k points)

Given an array of citations sorted in ascending order (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 citations each."


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


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

Follow up:

  • This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
  • Could you solve it in logarithmic time complexity?

Goeduhub's Top Online Courses @Udemy

For Indian Students- INR 360/- || For International Students- $9.99/-


Course Name



Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon


Natural Language Processing-NLP with Deep Learning in Python Apply Coupon


Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon
    More Courses

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
Best answer

Binary search

In this problem data is already sorted for you, so we should take advantage of it. What you think what you need to search in sorted data? The answer is binary search. Of course you can not apply it like this, you need to adapt it to our problem. Let us start with example [1,3,3,3,4,4,7] and then consider general case.








What is the answer fo this data? It is 3, because there is 3 publications with at least 3 citations:








I denoted found elements as O. We can see, that what we actually need to find, is the size of biggest square which is inside our sorted data. Mathematically speaking, we look for smallest index i, such that i + citations[i] >= n and then we return n-i. In our example n=7, i = 4 and answer is 7 - 4 = 3. How we find this smallest index i? Using binary search of course, because sequence i + citations[i] is non-decreasing.

We can not use bisect library here, because for this we need to calculate i + citations[i] for every i, which can be done only in O(n), so we need to apply vanila binary search by hands.


 time complexity is O(log n) and additional space complexity is O(1).

class Solution:

    def hIndex(self, citations):

        if not citations: return 0

        n = len(citations)

        beg, end = 0, n - 1

        while beg <= end:

            mid = (beg + end)//2

            if mid + citations[mid] >= n:

                end = mid - 1


                beg = mid + 1                

        return n - beg

eg :  ans = Solution()

3.3k questions

7.1k answers


4.6k users

Related questions

0 like 0 dislike
1 answer 100 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 378 views
asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 140 views
0 like 0 dislike
1 answer 807 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 1.6k views


About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © Social::   |  |