Is it only me or the brute force was difficult to understand?

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

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

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 < vec[low]) return k; if (k > vec[high] - n) return k + n;

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

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.

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

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

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

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

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

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.

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

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

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

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!

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

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

nice question, good approach

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

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

🤯 didn't thought for the binary search approach

This question can also be solved in LogN time complexity by the brute force code logic only code : int low = 0, high = arr.size()-1; int ans = k; while(low = arr[mid]) { ans = ans+mid-low+1; low = mid+1; } else { high = mid-1; } } return ans;

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

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

why this question is tagged easy on leetcode

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

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

Great explanation !

Crazy derivation sir! thank youu for the series

Very beautiful explained. With logic

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

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.

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

Pure Genius Explanation....

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

This guy's just incredibleee!

Nice question, learned a new concept.

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

After Watching 3 time I Finally understand

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

jab tak suraj chaand rahega , striver tera naam rahega

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

Brute force solution: public class Solution { public static int missingK(int[] vec, int n, int k) { // Write your code here. for(int i = 0;i

understood Thank you striver for such an amazing explanation

the brute force approach only works in cas1 not case 2

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

Bhaiya you are doing a great work ❤

there is always some question like this whose logic doesn't make sense.

Best explanation

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

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

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

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 :)

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 ?

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

Loved the explanation.

I dont think so that the brute force explained by him covers all cases, as when the array is sorted and the max element is equal to the number of element it will not be giving correct solution.

@striver //41. First Missing Positive (Leetcode).why this code does not work.. class Solution { public: int firstMissingPositive(vector& nums) { int k = 1; int low = 0; int high = nums.size() - 1; while (low = k) high = mid - 1; else low = mid + 1; } return k + high; } };

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

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

Thanks a lot Bhaiya . Crystal Clear

class Solution { public: int findKthPositive(vector& arr, int k) { int low = 0 , high = arr.size() -1 ,ans=k+high+1; if(arr[0]>k){ return k; } if(arr[high]-high-1

13:10 opposite polarity

great explanation for low+k.

awesome explanation

when are you planning to complete this series ?

Nice explanation Sir ❤❤❤

BRUTE FORCE let have array be [2, 3, 4, ,5] and find 5th missing number so the concept is let consider intially that all numbers are missing and if all numbers are missing then our fifth missing number will be x= 5 so now if we iterate over array and we consider 2(0th element of array) so now 2 is not missing anymore so now our 5th missing number will be x= 6 ,again on iterating we get 3 now our 3 is no more missing so now our 5th missing number will be x=7 ........... and in this process if we find any element of array greater then x(where x is 5th missing number) it means that 5th missing number which is x till now is lesser then current element of array hence it is our answer

i knew there was better algo than quick select thanks

where are notes as i m unable to find it in description?

your brute force solution is optimal solution for me 🤣🤣

UNDERSTOOD;

Striver one more correction * Time complexity O(log N ) for binary search 😅 but you said O(N). How comes nonody is mentioning it in comments ? am i wrong or something.

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

I coudln't think this way !! best solution

the brute force solution is beautiful.\

what if we are considering negative numbers in the array?

understood 😇

nicely explained bro ....thanks

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 Very Well!

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

Brilliant. Thanks!

Why is the time complexity O(N) ? It should be log base 2N. 😅

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

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

letsss goooo!! Understood

you are the best brother

Understood, thank you.

both approaches are very non intuitive ngl

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

Fantastic. Thank you.

Understood Sir.

TC of bs solution is logn

good question .. maza aya karke

understood

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

Brute force explanation was hard to understand. This is easier to grasp. def findKthPositive(arr, k): missing = [] i = 1 while len(missing) < k: if i not in arr: missing.append(i) i += 1 return missing[-1]