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...
this problem haunted me for a day, lucky I found your explanation, the optimal N = number of right hand side when (low>high) still need times to digest tho...
Thanks ! Everything about the binary search answer was perfect ! I am still not able to intuitively visualise how we return n - low at the end after the binary search ends. I get that it returns the right answer. But did not get how can one think about all of this say if one is in the middle of an interview. Why just n - low is returning the right answer and not say, n - low + 1 or n - low - 1 or any value added or subtracted to n - low
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)return n-i; } return 0;
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=(n-mid)){ result = n - mid; h -= 1; }else{ l +=1; } } return result; }
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& 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
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=count){ if(h
*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: 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;
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 citations [mid]: beg=mid+1 elif l-mid < citations [mid]: end=mid-1 ans = l-mid return ans
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
Doubt: if(citations[mid] == n - mid) { return citations[mid]; } In this condition, how are we pretty sure that citation[mid] will be answer, don't we need to search in the right for the more optimal one?
because we sorted the array in ascending or non-decreasing order. Any value greater than or equal to the search value will obviously be to the right hand-side of the search value
the confusion in your explanation is the fact that , we can only have h ranging from 1 to the length of the array, so in ur explanation there seems to be a bit of less clarity when you say v=7 or 8, since in those arrays h index 7 or 8 are not possible, only possible from 1 to 5 since size is 5.
This problem was incredibly difficult to understand. Just finding the h-index on pencil and paper was confusing, much less coding the algorithm. So stupid
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
In interviews, you will generally be required to write the function. In coding round, it is generally asked to implement a function because other things are very trivial. So, high chances are just to get to implement just your API.
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 ?
I think you did not understand the process. The first step is to search for value V if it is present in the array. If found then return it. If not found then move to 2nd step which is to return ''No if elements to the right of low including low''. Now, while performing step-1, you will take mid value = V. Now you will assume this as your answer and compare for its correctness. The question already mentions the definition of H-index. In (11,15) your mid will pick 11 and so if you assume it to be H-index then we should have atleast 11 papers with citations >= 11 but we have only 2. So, this is not a valid value for V and so we try to search for lower values. So high moves to the left of 1st element and we stop. Low is pointing to 1st element. So we move to step 2 and return no of elements to the right of low including low. This is how you get 2.
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...
Thanks bro :)
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!
Welcome :)
Seriously u made the problem super easy.Since evening i was struggling with the concept.
👍
who r u?
5 videos later I landed here, understood completely..kudos 👏👏
this problem haunted me for a day, lucky I found your explanation, the optimal N = number of right hand side when (low>high) still need times to digest tho...
Thanks for all the informative content you continue to provide Tech Dose!
Thanks man :)
Thanks ! Everything about the binary search answer was perfect ! I am still not able to intuitively visualise how we return n - low at the end after the binary search ends. I get that it returns the right answer. But did not get how can one think about all of this say if one is in the middle of an interview. Why just n - low is returning the right answer and not say, n - low + 1 or n - low - 1 or any value added or subtracted to n - low
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)return n-i;
}
return 0;
Nice. But the problem is challenging coz it asked to solve in Log time.
But u need to utilise the sorted property of array
Yes.... so i have changed my approach applying BS👍
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❤️❤️
🖖
Love you bro 💙👊 ✌️🔥💥🤘 Struggling with problem 3 hours yesterday with log(n) approach u made it easy
Welcome :)
I think this video is the only good explanation for this question. 🙏
Thanks 😅
one of the best explanation of this problem out there🔥🔥
Dude where do u work bro...i presume one of the top 4 companies....u r problem solving skills are on next level
😅 follow linkedIn or insta.
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=(n-mid)){
result = n - mid;
h -= 1;
}else{
l +=1;
}
}
return result;
}
how is it an optimization? you are moving h and l one at a time so it is not Binary search.
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& 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
Nice. But you should solve in logN as asked in the question.
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=count){
if(h
TLE bruhh
*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: 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
Really nice explanation. Thanks a lot
Thanks :)
amazing!!.. you are sooo good..❤💕😊
Thanks :)
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 citations [mid]:
beg=mid+1
elif l-mid < citations [mid]:
end=mid-1
ans = l-mid
return ans
Ans =l -mid is out of while loop
1:55, there are 3 papers with citations atleast >= 2
legendary explanation
Nice video, clear voice, great explanation.
Thanks :)
U made it look so easy!
Understood?
@@techdose4u CRYSTAL Clear 😎
Thanks bro
Awesome job. Thank you so much
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
Not possible to make it now bro.
Sir , please make a video on shortest superstring(leetcode 943) it's a nice problem and there is no solution for it available on TH-cam
Will try
Hey bro is there a list of must do questions on leetcode consisting of approx 300 problems..
Thanks..
Yes there is. I will make them after doing most problems.
Doubt:
if(citations[mid] == n - mid) {
return citations[mid];
}
In this condition, how are we pretty sure that citation[mid] will be answer, don't we need to search in the right for the more optimal one?
same doubt
because we sorted the array in ascending or non-decreasing order. Any value greater than or equal to the search value will obviously be to the right hand-side of the search value
in case of [0,1,2,3,4] how h = 2, there are 3 papers which have citations more than 2.
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):
e = m
m = (s + e) // 2
return h(m)
the confusion in your explanation is the fact that , we can only have h ranging from 1 to the length of the array, so in ur explanation there seems to be a bit of less clarity when you say v=7 or 8, since in those arrays h index 7 or 8 are not possible, only possible from 1 to 5 since size is 5.
👌👌👌👌👌
👍🏼
thanks
Welcome
This problem was incredibly difficult to understand. Just finding the h-index on pencil and paper was confusing, much less coding the algorithm. So stupid
Right 😅
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
In interviews, you will generally be required to write the function. In coding round, it is generally asked to implement a function because other things are very trivial. So, high chances are just to get to implement just your API.
@@techdose4u thanks brother you are a savior for me
😅
Can u please post the solutions for mockvita questions in cpp
I wish I got time 😅 Time is the constraint.
Sir Day 19 challenge?😅
Under process.
Plz, explain the other method which is more intuitive.
Which approach?
Can’t we just apply binary search to 0-N range? As in optimal case V=N, and this way we won’t have to use any extra trick.
what will be the O(n) solution?
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 ?
I think you did not understand the process. The first step is to search for value V if it is present in the array. If found then return it. If not found then move to 2nd step which is to return ''No if elements to the right of low including low''. Now, while performing step-1, you will take mid value = V. Now you will assume this as your answer and compare for its correctness. The question already mentions the definition of H-index. In (11,15) your mid will pick 11 and so if you assume it to be H-index then we should have atleast 11 papers with citations >= 11 but we have only 2. So, this is not a valid value for V and so we try to search for lower values. So high moves to the left of 1st element and we stop. Low is pointing to 1st element. So we move to step 2 and return no of elements to the right of low including low. This is how you get 2.
I really want to cry, just find it so hard to understand. Especially why n - low ?
I will tell you. Msg me :)
lower bound
class Solution {
public int hIndex(int[] a) {
int n=a.length;
int low=0;
int high=a.length-1;
int ans=-1;
while(low=a[mid]){
ans=a[mid];
low=mid+1;
}
else{
high=mid-1;
}
}
return Math.max(ans,n-low);
}
}
achaaaaaaaaaaaaaaaaa.................!!!!!!!!!!!!!!!
Hey all! How long you think problem of this level should take to solve and submit on average?
It depends on the solver level and also if you get the logic early. It's your strength or weakness and other factors. Let's see how others feel.
I was struggling with the problem statement itself :/