H Index II | Binary search | Leetcode #275



This video explains a very unique programming interview problem which is based on binary search algorithm.The problem is to find the H index of the papers given the citations of each paper in ascending order.We are required to find the maximum value V such that there are atleast V number of papers having atleast V citations.Linear search is a trivial approach for this problem and may lead to TLE.We cannot apply simple binary to find the optimal result.We need to make use of some observations in order to apply the binary search.I have shown all the observations and have solved the problem using simple binary search.I have explained it with example and have also explained code walk through at the end.I have solved using nested binary search technique as well and the code for both methods are provided in the same link.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful…CYA 🙂

=================================================================
INSTAGRAM:
LinkedIn:
=================================================================

CODE LINK:
SIMILAR PROBLEMs:-
Aggressive Cow:
Search Insert Position:

Nguồn: https://aj-watts.com/

Xem thêm bài viết khác: https://aj-watts.com/tong-hop/

  • Applied same approach but thought differently,
    it might be easy to digest
    Instead of taking the value of 'V' as the element we can take the value of 'V' as the index(mid index) itself,
    as maximum value of 'h' we can have is the len(citations)
    Below is my solution,it covers all the case and no need of any special case
    public int hIndex(int[] citations) {

    int len= citations.length;

    int start = 0;

    int end = len-1;

    int h = 0;

    int count = 0;

    while(start<=end){

    int mid = (start+end)/2;

    count = len-mid;

    if(citations[mid]>=count){

    if(h<count)

    h = count;

    end = mid-1;

    }else{

    start = mid+1;

    }

    }

    return h;

    }

    Ayush Goyal June 25, 2020 5:38 am Reply
  • Hey bro is there a list of must do questions on leetcode consisting of approx 300 problems..
    Thanks..

    Aman Kumar June 25, 2020 5:38 am Reply
  • what will be the O(n) solution?

    ashwani yadav June 25, 2020 5:38 am Reply
  • Sir Day 19 challenge?😅

    Himanshu Singh June 25, 2020 5:38 am Reply
  • Can u please post the solutions for mockvita questions in cpp

    Aakash Sharma June 25, 2020 5:38 am Reply
  • Nice video, clear voice, great explanation.

    Narendra yadav June 25, 2020 5:38 am Reply
  • Dude where do u work bro…i presume one of the top 4 companies….u r problem solving skills are on next level

    Bablu reddy June 25, 2020 5:38 am Reply
  • I have a very different question
    As i do practice on leetcode and gfg and there i need to complete the given function then in the online coding test or interview candidate has to write the whole code or just have to complete the function

    Ankit Singh June 25, 2020 5:38 am Reply
  • Sir , please make a video on shortest superstring(leetcode 943) it's a nice problem and there is no solution for it available on YouTube

    Ayush Garg June 25, 2020 5:38 am Reply
  • Love you bro 💙👊 ✌️🔥💥🤘 Struggling with problem 3 hours yesterday with log(n) approach u made it easy

    Shubham Agarwal June 25, 2020 5:38 am Reply
  • One day this content will be a warehouse to crack the coding interview for sure your thought process and explanation is really awesome keep up the great work…

    prince akhil June 25, 2020 5:38 am Reply
  • agin great explaination sir …..my solution take O(n)….but it is very simple.
    ..
    ….

    int n = citation.size();
    for(int i=0;i<n;i++){
    if(citations[i]>=n-i)return n-i;
    }
    return 0;

    PUNEET RAIPURIA June 25, 2020 5:38 am Reply
  • your approaches are really great . they helps me a lot thanks .
    I solved this using sliding window method . i think it will also be a simple approach in O(N) to solve it with a very small code and easily understandable .
    int hIndex(vector<int>& citations) {

    int n=citations.size();

    int l=0,r,ans=0; // l is the left pointer and r is the right pointer.

    for (r=0;r<n;r++)

    {

    while ((citations[l]<r-l+1||citations[r]<r-l+1)&&l<r)
    l++;
    if (citations[l]>=r-l+1&&citations[r]>=r-l+1)

    ans=max(ans,r-l+1);

    }

    return ans;
    }

    Rohit Kumar Rathore June 25, 2020 5:38 am Reply
  • The trick to find h index if it is not there in the array is too good. I got stuck there. The explanation really helped. Thanks!

    Lakshmy Subramaniam June 25, 2020 5:38 am Reply
  • Sir from where did you learn DSA when you were a beginner?

    himanshu jain June 25, 2020 5:38 am Reply
  • Thanks for the video. A little optimization on the second approach.

    public int hIndex(int[] citations) {
    int l = 0;
    int n = citations.length;
    int h = citations.length-1;
    int result = 0;

    while(l<=h){
    int mid = l + (h-l)/2;
    if(citations[mid]>=(n-mid)){
    result = n – mid;
    h -= 1;
    }else{
    l +=1;
    }
    }
    return result;
    }

    Somasundar Venkatesh June 25, 2020 5:38 am Reply
  • sir please make videos on leetcode weekly and biweekly contest 3rd and 4th questions 1st and 2nd are easy but we need some help on 3rd 4th questions in the contest

    Sahil choudhary June 25, 2020 5:38 am Reply
  • amazing!!.. you are sooo good..❤💕😊

    Amrutha P June 25, 2020 5:38 am Reply
  • This is what I read from WIKI and that made the problem very easy 🙂

    Formally, if f is the function that corresponds to the number of citations for each publication, we compute the h-index as follows: First we order the values of f from the largest to the lowest value. Then, we look for the last position in which f is greater than or equal to the position (we call h this position). For example, if we have a researcher with 5 publications A, B, C, D, and E with 10, 8, 5, 4, and 3 citations, respectively, the h-index is equal to 4 because the 4th publication has 4 citations and the 5th has only 3. In contrast, if the same publications have 25, 8, 5, 3, and 3 citations, then the index is 3 because the fourth paper has only 3 citations.

    f(A)=10, f(B)=8, f(C)=5, f(D)=4, f(E)=3 → h-index=4

    f(A)=25, f(B)=8, f(C)=5, f(D)=3, f(E)=3 → h-index=3

    [Source: https://en.wikipedia.org/wiki/H-index]

    Please read the above explanation!

    Here is my simple code

    public int HIndex(int[] citations) {

    int len = citations.Length;

    int low = 0;

    int high = len – 1;

    int mid;

    while(low <= high) {

    mid = low + (high – low) / 2;

    if(len – mid <= citations[mid])

    high = mid – 1;

    else

    low = mid + 1;

    }

    return len – low;

    }

    }

    Subham Raj June 25, 2020 5:38 am Reply
  • hi,i think you are getting something wrong ,at 6:29—6:38 you are saying v=7 it means atleast 7 papers having citations greater than equal to 7..I don't think this is the correct explanation of question because

    suppose input is [11,15] then according to your explanation not by code you are saying if v=11 then atleast 11 papers having citations greater than equal to 11 but here only 2 papers so by your explanation it is wrong.

    I have done it by own and have same strategy but i contradict with your statement what you are saying i think..Please correct me if i am taking it wrong ?

    Shubham Mahawar June 25, 2020 5:38 am Reply
  • Plz, explain the other method which is more intuitive.

    Carry June 25, 2020 5:38 am Reply
  • Your Examples are awesome sir!

    Sanjay S June 25, 2020 5:38 am Reply
  • Seriously u made the problem super easy.Since evening i was struggling with the concept.

    kartik mudgal June 25, 2020 5:38 am Reply
  • U made it look so easy!

    Spets Tech June 25, 2020 5:38 am Reply
  • achaaaaaaaaaaaaaaaaa……………..!!!!!!!!!!!!!!!

    Spets Tech June 25, 2020 5:38 am Reply
  • python code if someone need it.

    class Solution:

    def hIndex(self, citations: List[int]) -> int:

    if not citations:

    return 0

    def h(i):

    '''calculates h -index'''
    return min(n – i, citations[i])

    s = 0
    # start index
    n = len(citations)

    e = n – 1
    # end index
    m = (s + e)//2
    # mid index

    while e > s:

    if h(m) <= h(m + 1):
    # comparing h-index of papers at position(index) m and m + 1
    s = m + 1

    m = (s + e) // 2

    elif h(m) > h(m + 1):

    e = m

    m = (s + e) // 2

    return h(m)

    YOGENDRA JAISWAL 13110140 June 25, 2020 5:38 am Reply
  • I did it in python something like this, here l is the length of citations….
    l = len(citations)
    beg=0
    end = len(citations)-1
    while beg<=end:
    mid = int((beg+end)/2)
    if l-mid == citations [mid]:
    return citations [mid]
    elif l-mid > citations [mid]:
    beg=mid+1
    elif l-mid < citations [mid]:
    end=mid-1
    ans = l-mid

    return ans

    Sudhanshu Kumar June 25, 2020 5:38 am Reply
  • Hey all! How long you think problem of this level should take to solve and submit on average?

    YOGENDRA JAISWAL 13110140 June 25, 2020 5:38 am Reply
  • Your contents are helping me a lot vaiya…may this channel become a powerhouse to crack any placement interview. Thank you and lots of love❤️❤️

    sambhu mahato June 25, 2020 5:38 am Reply

Leave a Reply

Your email address will not be published. Required fields are marked *