SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
75 views
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."

Example:

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.

Note:

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?

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.

......X

......X

......X

....XXX

.XXXXXX

.XXXXXX

XXXXXXX

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

......X

......X

......X

....XXX

.XXXOOO

.XXXOOO

XXXXOOO

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.

Complexity:

 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

            else:

                beg = mid + 1                

        return n - beg

eg :  ans = Solution()
ans.hIndex([0,1,3,5,6])
Output-
3

Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

Related questions

0 like 0 dislike
1 answer 52 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 96 views
asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 23 views
0 like 0 dislike
1 answer 508 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 653 views

 Goeduhub:

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