BS-16. Kth Missing Positive Number | Maths + Binary Search
Problem Link: bit.ly/3p30UBg
Notes/C++/Java/Python codes:
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
Пікірлер: 277
Is it only me or the brute force was difficult to understand?
@bhalulal5947
Жыл бұрын
Same here bro I was frst shocked 😅
@tarunprajapati7642
Жыл бұрын
For me also
@kiranmoura2974
Жыл бұрын
Yes it is difficult
@elizabethr5161
Жыл бұрын
even I feel difficult.
@dhruv412
Жыл бұрын
same
correction: 21:18 time complexity should be O(logN)* . Great explanation though
Correction, @striver, at 2:45 the answer for arr=[5,7,10,12] and k=6 is 8 and not 7. Thanks for these series
@Bharat_Rider
10 ай бұрын
😂😂 this correction helped me so much🤣
@sidharthjain2129
9 ай бұрын
TBH it did help understand the brute force. Thanks mate.
@rounaq_khandelwal
9 ай бұрын
@@sidharthjain2129 welcome!
No doubt you explain nicely, everything gets crystal clear after going through your lecture video, but I wonder how do you come up with this type of solution on your own. It's like scientist making some mind boggling discoveries.
Understood! Super fantastic explanation as always, thank you so so much for your effort!!
I have never seen anything fantastic than this , I already enrolled in paid DSA course but trust me guys if I found out this channel and dsa sheet before that i have never taken the paid dsa course this is just awesome
Happy to solve without watching solution , took 4hrs to figure out approach and code it . Yeah happy me🙂
Thank you for the explanation. Two edge cases that should improve running time: if (k if (k > vec[high] - n) return k + n;
@Dev-x3b
Жыл бұрын
💯
you are far better than any of the comedians and so called celebrities . Thanks!
@swayamsharma7614
12 күн бұрын
in what sense you are comparing ?
Optimal one is just out of the box kind of thing ❤
@shreyxnsh.14
6 ай бұрын
yeah, you can only solve this question in the interview if you have solved it before
@Ayush37262
5 ай бұрын
@@shreyxnsh.14 Thanks bhai, Solve nhi ho rha tha aur easy tag dekh kar depressed feel ho rha tha...
@saswatrath4646
3 ай бұрын
@@Ayush37262 Many easy problems are actually hard so don't be demotivated if you can't solve an easy rated problem, it's because it's not easy at all.
Awesome explanation man, after some self dry run of few examples, I completely got the concept. Thanks!
Very beautiful explained. With logic
brute force assume you have an empty array and we have some k value, say k = 4the missing number, so in this case the missing value would be 4 Case 1:- where the value at a index in the array now just consider the empty array again and we added a number smaller than k to it, say 2, so now when we again try to find the 4th missing number we would get it as 5 ( as 1 3 4 5 , as 2 already present in the array, hence the missing value shifts by one position ahead and 5 is the 4th missing value), hence whenever we get a number in the array smaller than k, the kth missing value shifts by position ahead Case2 :- where value at a index in array > k now consider empty array again and we added a number greater than k, assume k = 4 and we added 7 to it, here the kth missing element will be 4 itself, as even though seven was added - it indicated that the array might or might not contain the first 6 numbers and as the k = 4 value is lesser than 7, so this kth value would also come under missing value, and as 7 > k, so no effect on k occur. So k is the missing element
understood Thank you striver for such an amazing explanation
🤯 didn't thought for the binary search approach
Crazy derivation sir! thank youu for the series
Pure Genius Explanation....
Great explanation !
Bhaiya you are doing a great work ❤
For [4,7,9] and k = 3, answer will be simple that is 3, bcz k And at the end we can use arr[high] like:- " int diff = (arr[high] - high + 1); int miss = k - diff; return arr[high] + miss; "
@takeUforward
Жыл бұрын
Yes you can do this as well
@003_baneshubhamvijay3
Жыл бұрын
int diff = arr[high] - (high + 1); int miss = k - diff; return arr[high] + miss; A small correction in parenthesis**
@sukhii0220
Ай бұрын
how does this works ? where we would write this after when high cross low ?
@sukhii0220
Ай бұрын
@@003_baneshubhamvijay3 how does it working ? it gives 6 if we apply in [4, 7,9] and k=3
great explanation for low+k.
This guy's just incredibleee!
Loved the explanation.
thankfully I was able to do it by my own. I was able to think this approach myself
how beautifully u explained the brute force. top level intuition👑.
The subtlety in the algorithm is not considering (arr[mid] - (mid+1) == k) coz if we hit that we have no way to figure out the answer(take k=1 as example and your arr[mid]-(mid+1) matches with k, that is why there is no condition for equals k. Idea is to move high to the index where the missing numbers are lesser than k, that way we get the low end and all we got to do is add the remaining. would have been good if this point was insisted coz if you forget the algorithm and try to write from scratch thinking oh it's binary search, you're gonna get stuck in an interview.
@harshitpandey8304
10 ай бұрын
I agree
@saswatrath4646
3 ай бұрын
great observation, it will help me memorize this algorithm better, thanks!
simple problem koo completed or comopleted problem koo simple, bana koi aap sai sikhai, you are master of dsa🤩🤩🤩🤩❤❤❤❤❤❤❤❤
Understood Very Well!
Thanks a lot Bhaiya . Crystal Clear
nicely explained bro ....thanks
Brilliant. Thanks!
@takeUforward maybe you can update the time complexity in description for binary search as O(log2N)
Literally, I spent one day trying to solve the brute force but when I saw the brute force in the video I was shocked how is it possible?😐😐
For brute force in the array 5,7,10,12 k=6. For 5 -> k=7, 7 -> k=8, 10 exceeds the value hence k becomes 8 and 8 should be returned. Hope this helps!
amazing solution , maja agya
Understood Bhaiya ..!!
awesome explanation
bar bar dekho... hazaar bar dekho or practice kro is the key here
this question scared the living daylights out of me, couldn't solve it even brute force was this really an easy question
letsss goooo!! Understood
Fantastic. Thank you.
you are the best brother
i knew there was better algo than quick select thanks
Nice explanation Sir ❤❤❤
Totally dependent on you bro ❤
Understood, thank you.
Understood Sir.
good question .. maza aya karke
I coudln't think this way !! best solution
Helped a lot 🙂🙂😌
Best explanation
when are you planning to complete this series ?
Understood✅🔥🔥
Awesome Sir......
why this question is tagged easy on leetcode
@VivekYadav-uy9ts
7 ай бұрын
Bacause of the contraints, there the array size is given between 1 to 1000 only, so you can just simply traverse the whole array and can find k'th missing element!
understood 😇
21:23 error time complexity will be o(log base 2 n) that is o(log n)
Legendary Boss
Understooooooood!
the brute force solution is beautiful.\
after a good brainstorming session it's time to see the video :)
@Ayush37262
5 ай бұрын
Did you solved the question before watching solution??
@dogwoofwoof8154
5 ай бұрын
@@Ayush37262 yep
@Ayush37262
5 ай бұрын
@@dogwoofwoof8154 You are Batman!
thank you so much sir
understood!
Thank you so much!! this is one of the trickiest binary search problem which I was able to figure out on my own. class Solution { public int findKthPositive(int[] arr, int k) { if(k return k; } int low = 0; int high = arr.length-1; while(low
@sukhii0220
Ай бұрын
this existingdifff is the difference between the range we find out ?
how in explanation high
Understood ❤
Understood !! 😎😎
Hey Bhagwan , The BS intuition great
I just wonder this is only first video bit difficult to understand both brute force and optimal.
Thank you Bhaiya
Both the solutions are difficult to grasp at first go. It needs another revisit for sure
@shreyxnsh.14
6 ай бұрын
faxx, how is your dsa prep now btw?
An easier brute force code:- int missingK(vector vec, int n, int k) { // Write your code here. int i=0,j=1,missing=0; while(missing!=k){ if(vec[i]!=j){ missing++; j++; } else{ i++, j++; } } j--; //We did this because j moved 1 forward because of the if statement. So to get our answer, we need to move j backward by 1. return j; }
@thedon713
8 ай бұрын
we learn here how to implement binary search not only how to solve in this specific problem.
@rishabh_pant
7 ай бұрын
its perfect
@shrinikclub8883
7 ай бұрын
there is a potential issue in your code. The j-- statement before returning the result might cause incorrect results. If the loop exits because missing equals k, then j should already represent the k-th missing positive number. Decrementing it before returning could lead to incorrect results.
Bhaiya the GfG link to the question in a2z DSA Sheet the question is bit different to what explained in video for example in the test case n = 3 , k=1 {32 , 59 ,77} the first missing number is 33
Understood!!
After Watching 3 time I Finally understand
@dhamotz4737
16 күн бұрын
can you explain why are we using missing=arr[I]-[I+1] , for finding the missing numbers ? cause this formulae is setting in the question but as I am customising the values in the question the missing numbers don't come? can u give some test cases in which you are getting answer for this formula only sp that I can approve that this formulae works for every possible cases not only what he has given there
******** ONE OBSERVATION ********* what if the number of missing elements = k , i.e. int missing = arr[mid]-(mid+1); missing == k can we write this: if(missing
your brute force solution is optimal solution for me 🤣🤣
understoood :)
understood
at 21:17 , time complexity would be O(logn) [ just a human error]
Understood🙃
can someone explain me the missing number formulae in the brute force as its setting correct for the case which striver has taken but once I am changing the values in the array and trying to find the new missing number I am not getting what I should get, did I get the question in a wrong manner , am I missing any key point of the question ?
Understand 🎉
the optimal solution definitely does not fit in the easy category striver 😂 btw amazing lecture🙏🏻♥
Understood
Understood :)
what if the input arr[]=[2] and k=1 ? According to this logic i think answer is 2 but actully it is 1....
at 19:45 sir have taken value of "more" as arr[high]-high-1 but should it be arr[high]-high+1?.....can anyone plz explain??
why cant we use arr[mid] -- (mid + 1 ) formula to calculate the missing number instead of the formula arr[high ] -- (high + 1) ??
intuition behind incrementing k is not clear, are we assuming kth element is k inititally and why incrementing k leads to answer, i understood the code but intuition is not clear
just one question though, we are finding missing via arr[mid]-mid+1; why are we using using arr[high] ?? like fore expression arr[high]-high+1 ?? arr[high]+more ??
@magdeline1207
10 ай бұрын
the purpose of binary search using mid is to let high point to idx in arr where there are fewer number of missing int than k, for eg. arr[high] point to idx where there are 3 missing before that idx, and we just use arr[high]+ (k-missing) to find the answer, since (k-missing) is the number of missing int on the right of arr[high]
Bro by when your whole dsa sheet will be covered, placement coming up?any eta approx?
@adityakanwar8370
Жыл бұрын
+1
For brute force this case 2,5,6,7,9 and k=5 will fail.. correct me..
GodLike!
woozy of a question
Why does it not work on gfg?
where are notes as i m unable to find it in description?
bhaiya bs ques tha ki : jaise aap figure out krrh ho ki 1,2,3,4 ideally 4,7,9,10 arr m hone chaiye the. so inko substract kre to missing number milenge. iska logic nhi bnra dry run krte wkt. mtlab wo missing number maths se aara h but kaise aaya ye nhi feel ara..
13:10 opposite polarity
bhaiya iska link mein galat question ka code hai aur sheet mein link bhi nahi hai