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/
Xem thêm Bài Viết:
- HƯỚNG DẪN LÀM DẤU TÍCH CUỐI VIDEO TIKTOK CỰC DỄ
- USB WIFI Không Dây Giá 125k Trên Shoppe Chất Lượng NTN – Nguyễn Quỳnh Vlogs
- Picsart| Cách làm ảnh bìa Facebook đẹp, cách làm ảnh bìa nghệ thuật
- Cách dùng hàm Choose trong Excel
- Xem Ngày Tốt Tháng 9 năm 2017 tháng 7 âm lịch từ ngày 28 đến 30 | Tử Vi Trọn Đời
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;
}
Hey bro is there a list of must do questions on leetcode consisting of approx 300 problems..
Thanks..
what will be the O(n) solution?
Sir Day 19 challenge?😅
Can u please post the solutions for mockvita questions in cpp
Nice video, clear voice, great explanation.
Dude where do u work bro…i presume one of the top 4 companies….u r problem solving skills are on next level
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
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
Love you bro 💙👊 ✌️🔥💥🤘 Struggling with problem 3 hours yesterday with log(n) approach u made it easy
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…
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;
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;
}
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!
Sir from where did you learn DSA when you were a beginner?
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;
}
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
amazing!!.. you are sooo good..❤💕😊
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;
}
}
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 ?
Plz, explain the other method which is more intuitive.
Your Examples are awesome sir!
Seriously u made the problem super easy.Since evening i was struggling with the concept.
U made it look so easy!
achaaaaaaaaaaaaaaaaa……………..!!!!!!!!!!!!!!!
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)
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
Hey all! How long you think problem of this level should take to solve and submit on average?
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❤️❤️