BS-16. Kth Missing Positive Number | Maths + Binary Search

[@karanhaldar755]

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

[@abhishekshinde5375]

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 < k 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

[@harrisjutt5021]

Thank you very much man 💜💜

[@crazymemes4080]

thanks bro, i got it :)

[@AmeyRakhe]

BRO THANK YOU SOO MUCH, really I got the brute force after i read this comment

[@Fe-ironman]

this is another easy brute force approach 3 5 7 is the array then if k =4 then find max in array which is 7 then run loop from 1 to 7 then have a counter "missingpoint" another countr track to keep track of array elements then now do this for i = 1 to 7 ; i++ if(i==arr[track]){ track++; } else{ missingpoint++; if(missingpoint==k) then return i; }

[@t3ch_r4id]

Nice 👌🏻

[@rounaq_khandelwal]

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]

😂😂 this correction helped me so much🤣

[@sidharthjain2129]

TBH it did help understand the brute force. Thanks mate.

[@rounaq_khandelwal]

@@sidharthjain2129 welcome!

[@tomtanner4013]

Thanks

[@sauravchandra10]

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

[@Anony.musk01]

correction: 21:18 time complexity should be O(logN)* . Great explanation though

[@alessandrocamilleri1239]

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;

[@Dev-x3b]

💯

[@aryansinha1818]

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.

[@varunpalsingh3822]

Optimal one is just out of the box kind of thing ❤

[@shreyxnsh.14]

yeah, you can only solve this question in the interview if you have solved it before

[@Ayush37262]

​@@shreyxnsh.14 Thanks bhai, Solve nhi ho rha tha aur easy tag dekh kar depressed feel ho rha tha...

[@saswatrath4646]

@@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.

[@mittal_aaditya]

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!

[@sayakghosh5104]

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; "

[@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

[@kiranpoojary493]

I used this logic before watching complete video, its give index error if high goes negative

[@saketjaiswalSJ]

21:23 error time complexity will be o(log base 2 n) that is o(log n)

[@kirannagulakonda3443]

Happy to solve without watching solution , took 4hrs to figure out approach and code it . Yeah happy me🙂

[@prathamsharma4802]

you are far better than any of the comedians and so called celebrities . Thanks!

[@swayamsharma7614]

in what sense you are comparing ?

[@hx-ql3de]

so you watch striver for entertainment and comedy purpose?

[@srinivas1694]

What is wrong with you lol

[@shamanthhegde2820]

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

[@sukhii0220]

this existingdifff is the difference between the range we find out ?

[@ShahNawaz-cx3pi]

******** 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

[@cinime]

Understood! Super fantastic explanation as always, thank you so so much for your effort!!

[@purushottam108]

simple problem koo completed or comopleted problem koo simple, bana koi aap sai sikhai, you are master of dsa🤩🤩🤩🤩❤❤❤❤❤❤❤❤

[@bhaskararya9112]

Awesome explanation man, after some self dry run of few examples, I completely got the concept. Thanks!

[@sagarsrivastava1236]

Pure Genius Explanation....

[@samreenimam8608]

bar bar dekho... hazaar bar dekho or practice kro is the key here

[@vedikamishra009]

😂

[@RaunitJaiswal-s9v]

"Guys, look, brute force isn't hard; it's just that it's very basic. If you observe, 10-15 questions are medium or hard, even with brute force, but their brute force and better optimal solutions are all basic. That's why it feels this way. It's just like making an observation and then giving it a method or property name, and that's it."

[@simply_akh1l]

nice question, good approach

[@santhosh7042]

🤯 didn't thought for the binary search approach

[@animeshtripathi6916]

Irony is that i found optimal solution easier than brute force

[@jyoti3427]

this question was really hard, even brute force was also hard, but finally understand

[@AS-gf3ci]

Both the solutions are difficult to grasp at first go. It needs another revisit for sure

[@shreyxnsh.14]

faxx, how is your dsa prep now btw?

[@JacquesAsinyo-e5i]

you are such a good teacher!!

[@dayashankarlakhotia4943]

Very beautiful explained. With logic

[@abhishekkunal8958]

Binary search done and dusted ❤

[@ipshitatandon5134]

Crazy derivation sir! thank youu for the series

[@U2011-n7w]

why this question is tagged easy on leetcode

[@VivekYadav-uy9ts]

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!

[@CodeMode9313]

Habibi batai toh mast hai tum ....correction :) @ 21:18 time stamp ie TC be logn

[@yoMisterWhyte]

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]

I agree

[@saswatrath4646]

great observation, it will help me memorize this algorithm better, thanks!

[@girikgarg8]

Great explanation !

[@nikhilneogy289]

Beautiful explanation.

[@immrhrr]

thankfully I was able to do it by my own. I was able to think this approach myself

[@lostcyrus8578]

Bhaiya you are doing a great work ❤

[@Akhilkumar0024]

this question scared the living daylights out of me, couldn't solve it even brute force was this really an easy question

[@bhanusingh4351]

at 21:17 , time complexity would be O(logn) [ just a human error]

[@dipanshuraj7868]

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?😐😐

[@vedikamishra009]

same

[@dipanshuraj7868]

@vedikamishra009 yeah 😅

[@PeeyushSharma-pc8fc]

the optimal solution definitely does not fit in the easy category striver 😂 btw amazing lecture🙏🏻♥

[@thetrueworld-q6m]

Extreme tough problem ! Seeing it marked as "easy" on LC was demotivating

[@adityamaurya6646]

This guy's just incredibleee!

[@preritphoenixgupta330]

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.

[@pulkitjain5159]

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

[@preritphoenixgupta330]

@@pulkitjain5159 okay, thanks bhai

[@saketsoni2587]

stack me sirf monotonic stack wala ek concept hai jo baar baar dikh jata sawalo me, wo largest histogram wale me covered hai

[@preritphoenixgupta330]

@@saketsoni2587 Ok Thanks

[@Josuke217]

Nice question, learned a new concept.

[@dogwoofwoof8154]

after a good brainstorming session it's time to see the video :)

[@Ayush37262]

Did you solved the question before watching solution??

[@dogwoofwoof8154]

@@Ayush37262 yep

[@Ayush37262]

@@dogwoofwoof8154 You are Batman!

[@K_EN_VisheshSaini]

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; }

[@thedon713]

we learn here how to implement binary search not only how to solve in this specific problem.

[@rishabh_pant]

its perfect

[@shrinikclub8883]

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.

[@sanjayv-ef6ey]

understood bro and thanks for clarificationn for l+k

[@msiddhu45]

Great explanation.

[@AtulKumar-c4x7l]

understood Thank you striver for such an amazing explanation

[@khushwantkumar800]

For Brute Force assume the array is 2 3 4 7 11 and K is 2, then the second missing number should be 5, but as per brute force logic, it's coming different

[@akworld2739]

your brute force solution is optimal solution for me 🤣🤣

[@tridibeshmisra9426]

good question .. maza aya karke

[@gowthamvegi608]

Great Explanation!

[@theindianshady]

13:00 isn't it the violation of the binary search rule . Where high surpasses the low or vice verse

[@ayushpratapsingh2540]

That is where we come out of the loop and calculate our answer as k + high + 1

[@theindianshady]

@@ayushpratapsingh2540 Thanks buddy. I got this yesterday while doing the question ♥️

[@MusaafirSonu]

The time complexity of the given code is O(log n), where n is the size of the input array arr. Explanation: The code uses a binary search algorithm, which typically operates in O(log n) time complexity. The loop runs as long as low

[@ayushmanpaul3931]

great explanation for low+k.

[@playwithlinux]

Nice explanation Sir ❤❤❤

[@VishalGupta-xw2rp]

13:10 opposite polarity

[@rushilvyas9869]

Loved the explanation.

[@happyteen7195]

how beautifully u explained the brute force. top level intuition👑.

[@DeepakPatel-d5v]

Thanks a lot Bhaiya . Crystal Clear

[@PremShinde-p4q]

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??

[@harshdiwase1941]

I coudln't think this way !! best solution

[@dank7044]

the brute force solution is beautiful.\

[@k18-y5e]

i knew there was better algo than quick select thanks

[@thedon713]

you are the best brother

[@umangkumar2005]

int missingK(vector < int > arr, int n, int k) { int low=0; int high=n-1; int mid=low+(high-low)/2; while(low

[@ankitgupta7467]

Hey Bhagwan , The BS intuition great

[@lokeshnegi5051]

awesome explanation

[@badrirao6472]

why cant we use arr[mid] -- (mid + 1 ) formula to calculate the missing number instead of the formula arr[high ] -- (high + 1) ??

[@prakharsahu5778]

when are you planning to complete this series ?

[@pulkitjain5159]

amazing solution , maja agya

[@Gaurav_Tripathi_]

Understood Bhaiya ..!!

[@jaganmohan2198]

nicely explained bro ....thanks

[@amitfritz11]

I just wonder this is only first video bit difficult to understand both brute force and optimal.

[@AnmolGupta-oj4lm]

Understood Very Well!

[@Ehvrbumtf2dwwrgeyhtumruh]

Should array be strictly increasing?

[@dronnema203]

I have a doubt! when we have already said that low

[@seekingsoul871]

Best explanation

[@mohammedowais8768]

Until last video Everyone: I was able to solve this without your help!🥳 Pattern changes a bit, Everyone: Why is the brute force solution so difficult??🥵

[@culeforever5408]

understood 😇

[@shubhamsingh4701]

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]

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]

[@Shunya_Advait]

Understood Sir.

[@rohandas6298]

int missingK(vector < int > vec, int n, int k) { int low=0,high=n-1; while(low

[@sukhii0220]

arr[mid] - (mid+1) was the formula found out before to find missing nums , then change to arr[high] -(high+1) how ????

[@nousad-ali-0]

After Watching 3 time I Finally understand

[@dhamotz4737]

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

[@lucario404]

@takeUforward maybe you can update the time complexity in description for binary search as O(log2N)

[@ReD4eva94]

Brilliant. Thanks!

[@mikedelta658]

Fantastic. Thank you.

[@gauarv608]

the brute force approach only works in cas1 not case 2

[@ritikanand3425]

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

[@anshulrawat3458]

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..

[@NazeerBashaShaik]

Understood, thank you.

[@Manishgupta200]

Optimal code takes much time to understand

[@sarangkumarsingh7901]

Awesome Sir......

[@dhruvbhati1347]

At 2:30 minutes , the 6th missing number should be 8 not 7, I think you missed it by mistake. Btw great content, thank you!

[@tarunprajapati7642]

No, he is doing right. The thing is that logic is difficult to understand at first time.

[@lucario404]

you are right

[@rahulkarki6857]

Totally dependent on you bro ❤

[@srija0608]

Understood 👍

[@YourCodeVerse]

Understood✅🔥🔥