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

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.

You can follow me across social media, all my handles are below:

0:00 Introduction of Course

[sauravchandra]

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

[kirannagulakonda]

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

[abhishekshinde]

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

[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 <3 🥰

[Anony.musk]

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

[aryansinha]

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.

[alessandrocamilleri]

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;

[sayakghosh]

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

[varunpalsingh]

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

[karanhaldar]

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

[dipanshuraj]

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

[prathamsharma]

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

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

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

[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 <= high, and in each iteration, it halves the search space by adjusting the low and high pointers based on the number of missing elements up to the mid index.
The key operation inside the loop, calculating mid and missing, both take constant time, O(1).
Thus, the overall time complexity is dominated by the binary search process, which is O(log n).

[saketjaiswal]

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

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

[ShahNawaz-cxpi]

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<=k){
low = mid+1;
}
else
high = mid-1;
}

The answer is NO, why ?
Dry run the given testcase:-
arr = [2], k = 1

The upper code will give 2 as answer but we can see the answer should be 1,

We have to write :
if(missing<k){
low = mid+1;
}
else
high = mid-1;
}
Because, the polarity gets swaped when the binary search is over (explained in many previous videos).
When binary search ends the high should point at maximum_not_possible_answer and low should point at minimum_possible_answer.

Yes offcourse there are many ways to handle this case even without considering polarity.

[samreenimam]

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

[purushottam]

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