BS-16. Kth Missing Positive Number | Maths + Binary Search
Vložit
- čas přidán 22. 06. 2023
- 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
Is it only me or the brute force was difficult to understand?
Same here bro I was frst shocked 😅
For me also
Yes it is difficult
even I feel difficult.
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
😂😂 this correction helped me so much🤣
TBH it did help understand the brute force. Thanks mate.
@@sidharthjain2129 welcome!
Optimal one is just out of the box kind of thing ❤
yeah, you can only solve this question in the interview if you have solved it before
@@shreyxnsh.14 Thanks bhai,
Solve nhi ho rha tha aur easy tag dekh kar depressed feel ho rha tha...
@@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.
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!!
you are far better than any of the comedians and so called celebrities . Thanks!
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
simple problem koo completed or comopleted problem koo simple, bana koi aap sai sikhai, you are master of dsa🤩🤩🤩🤩❤❤❤❤❤❤❤❤
Very beautiful explained. With logic
Thank you for the explanation.
Two edge cases that should improve running time:
if (k < vec[low]) return k;
if (k > vec[high] - n) return k + n;
💯
understood
Thank you striver for such an amazing explanation
Pure Genius Explanation....
For [4,7,9] and k = 3, answer will be simple that is 3, bcz k < arr[0] for all these cases we can directly return 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; "
Yes you can do this as well
int diff = arr[high] - (high + 1);
int miss = k - diff;
return arr[high] + miss;
A small correction in parenthesis**
Bhaiya you are doing a great work ❤
great explanation for low+k.
After Watching 3 time I Finally understand
Loved the explanation.
🤯 didn't thought for the binary search approach
Thanks a lot Bhaiya . Crystal Clear
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.
I agree
great observation, it will help me memorize this algorithm better, thanks!
Nice explanation Sir ❤❤❤
nicely explained bro ....thanks
Understood Very Well!
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!
how beautifully u explained the brute force. top level intuition👑.
Brilliant. Thanks!
@takeUforward maybe you can update the time complexity in description for binary search as O(log2N)
i knew there was better algo than quick select thanks
Fantastic. Thank you.
I coudln't think this way !! best solution
Understood, thank you.
amazing solution , maja agya
Happy to solve without watching solution , took 4hrs to figure out approach and code it . Yeah happy me🙂
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 < arr[0]) {
return k;
}
int low = 0;
int high = arr.length-1;
while(low
you are the best brother
Helped a lot 🙂🙂😌
good question .. maza aya karke
Understood Bhaiya ..!!
Understood Sir.
Totally dependent on you bro ❤
21:23 error time complexity will be o(log base 2 n) that is o(log n)
bar bar dekho... hazaar bar dekho or practice kro is the key here
the brute force solution is beautiful.\
when are you planning to complete this series ?
thank you so much sir
Awesome Sir......
Thank you Bhaiya
An easier brute force code:-
int missingK(vector < int > 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;
}
we learn here how to implement binary search not only how to solve in this specific problem.
its perfect
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.
Understood !! 😎😎
Understood✅🔥🔥
understood 😇
Understood!!
understood!
after a good brainstorming session it's time to see the video :)
Did you solved the question before watching solution??
@@Ayush37262 yep
@@dogwoofwoof8154 You are Batman!
why cant we use arr[mid] -- (mid + 1 ) formula to calculate the missing number instead of the formula arr[high ] -- (high + 1) ??
Legendary Boss
Understood ❤
Understooooooood!
understood
Understand 🎉
Understood
at 21:17 , time complexity would be O(logn) [ just a human error]
Hey Bhagwan , The BS intuition great
how in explanation high
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?😐😐
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
Both the solutions are difficult to grasp at first go. It needs another revisit for sure
faxx, how is your dsa prep now btw?
Hi Striver, I'm a final year student and our placement season is coming soon can you give some tips. Also, there are some topics which I need to work upon like Stack n Queues when can we expect those series/ playlist from You. I like your way of teaching and approach, I know you are caught up with a lot of work but if you could bring those series soon or suggest some alternatives that would be great.
bhai stack m mujhe bhi dikkat aai thi par bhaiya ka largest histogram wala solution dekhna , dono parts , then leetcode ke question lagana nahi aaye toh uske solution dekhle , fhir aane lagega comfidence m bhi yahi kara hu bhai
@@pulkitjain5159 okay, thanks bhai
stack me sirf monotonic stack wala ek concept hai jo baar baar dikh jata sawalo me, wo largest histogram wale me covered hai
@@saketsoni2587 Ok Thanks
******** 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
why this question is tagged easy on leetcode
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!
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
Understood🙃
understoood :)
13:10 opposite polarity
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..
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 ??
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]
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??
Bro by when your whole dsa sheet will be covered, placement coming up?any eta approx?
+1
what if the input arr[]=[2] and k=1 ? According to this logic i think answer is 2 but actully it is 1....
Optimal code takes much time to understand
I just wonder this is only first video bit difficult to understand both brute force and optimal.
GodLike!
your brute force solution is optimal solution for me 🤣🤣
int missingK(vector < int > vec, int n, int k) {
int low=0,high=n-1;
while(low
For brute force this case 2,5,6,7,9 and k=5 will fail.. correct me..
bhaiya iska link mein galat question ka code hai aur sheet mein link bhi nahi hai
Habibi batai toh mast hai tum ....correction :) @ 21:18 time stamp ie TC be logn
Bhaiya ek request thi app se🙏 ... A2Z DSA Sheet me GFG ke question ka link hatne ke karan bahut problem ho raha hai , abhi mai apke ke sheet se approx 250 problem GFG plateform pe kar chuka hoon but ab sheet se GFG ke problems ka link hatne ke karan question ko revist karne me bahut problem ho raha hai ... I think aap mere problem ko samajh pa rahe honge ...So please bhaiya 🙏🙏🙏🙏 GFG ke problems ka bhi link add karva digiye 🙏🙏🙏🙏
int missingK(vector < int > arr, int n, int k) {
int low=0;
int high=n-1;
int mid=low+(high-low)/2;
while(low
TC of bs solution is logn
Before u see this video think with different examples by how can we eliminate one half (FINISHED) . If you understand the opposite polarity concept (unless u can't without paper pen ) this question is piece of cake ; I took 1 hr to solve :)
I didnt get it
for array 2 3 4 7 11
once we exit the while loop our arr[high] is 7 but missing is pointing to the last index so isnt missing 11 - i -1 = 6?
how r u considering missing equal to 3?
Bro if you take 11 for consideration to calculate the final answer( kth value ) , so in that case it won't give you the correct answer( kth value) , that's why he has taken 7 and calculate the missing number further to find the kth value :)
Why does it not work on gfg?
Undertsood
bruhh howTf did you thibk of that solution! It was insane.
Understood. But it is difficult.
Another related approach
class Solution {
private:
int possible(int low ,int mid,unordered_map& mp,int k){
int count =0;
for(int i=low;i
❤
there is always some question like this whose logic doesn't make sense.