the same question they asked me in round 2 of sde 2. I gave an answer of O(N), then suddenly they wanted an answer without extra spaces!! I stucked forever there. 😶
@@sjchat That's great. At least you reached the managerial round. I had my heart in my mouth when you said you couldn't come up with constant space solution.
I was asked this as my first question on my Round 1 of Amazon interview and I gave the O(max(element)) soln and he was satisfied. He asked me to optimize it further but was not able to do it. Thanks Rachit for doing such a wonderful solution.
We can apply the first approach on -ve elements as well by using shifting. shift all -ve values to front and then apply the 1st approach you mentioned for +ve numbers in array.
@@HarshGangwar consider an array of size n with fist n/2 elements positive and last n/2 elements negative. So to move all the last n/2 elements to front ,each of the last n/2 elements will have to traverse a distance of n/2 i.e O(n/2 * n/2) = O(n^2). Eg : [1,2,3,4....500,-1,-2,-3...-500] To move -1 to pos 0 takes n/2 ops and similarly for all rem negative elements.
@@rohankrishnaullas6705 the approach you are explaining is shifting. You can just swap every negative element you encounter to the jth index(initially 0) and then increment the value of j. This will be O(n)
for anyone looking for a bit simpler code, with the same idea while(i < A.length){ if(A[i] == i+1 || A[i] A.length) i++; else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1); else i++; } i = 0; while(i < A.length && A[i] == i+1) i++; return i+1;
This solution was amazing. I saw a question where the array was sorted and we had to find the mex in log(n) time. I guess we can simply find the point where difference between index and the number is 1 using binary search
Yes, we can use binary search. I think it can be done like this - Lets set l = 1 and r = n+1 for binary search. Then the number we predict as our ans will be mid. Then if the index of number is having number larger than it then our ans might be this mid and since we need to minimize we shift r towards mid. If the index equals the value then we should move our l towards mid. During the process we can keep track of minimum and get our ans
In addition to the first approach, we can change the 0s and negatives to Array Size + 1 and then iterate in the array to make the postive numbers negative. After that, we can return the index (i+1 actually) of the first negative number found.
When I started the video and think of the solution I got the XOR solution but then you threw the O(1) limit then I got stuck😅😅, As always Amazing video Rachit 😎🔥🔥
For the case of all +ve numbers, if the array had repetitions say, arr =[1, 1], arr will become [-1,1] first and then [1,1] on multiplying by -1. We will get an answer as 1 when it should be 2. So multiplying by -1 should happen only when the element at that index is positive.
To solve this segeregate the negative from positives ..keep your negativity to left part of array and then apply the first algo taught in this video on the positive part
As the array can be modified then all the "non positive" numbers can be replaced with N+1 (N=size of the array). Then I think the previous approach will work.
we can make all -ve and > N numbers as 0 and rest all numbers occurrence will be marked as 1 in that index. and the first index which has 0 that is the missing
When I was watching this video I also came up with an approach that if size is N and there is no copy then at max N+1 could be the mex so we can store the sum of N numbers let tmp = (N+1)*(N)/2 and now iterate over the entire array if the value is less than N and greater then 0 decrease the value of tmp with that value , after iteration if the tmp is 0 ans should be N+1 else ans will be tmp
Will it goes to o(n ^ 2) in the worst case? One traversal for o(n) and inside that we are doing swap which could be for n -1 elements? Example array = [3, 4, 2, 9] at 10:50 you say same
Great explanation, but fails for the array with repeated numbers, for ex. [1, 3, 6, 4, 1, -2]. As it swaps with the element at correct position, it enters infinite loop on the 2nd occurrence of 1.
If I sort the array in ascending order like 1,3,4,7. Then iterate to check the difference between consecutive digits(3-1,4-3,7-4 etc). For the first difference that is >1, I add 1 to the left hand side value(1+1), to get the smallest number.
Exactly that what i was thinking...it will surely fail for duplicates.........to solve this segregate the positive and negative numbers (keep all the negatives to left of positives)and then apply the first algo on the positive part
An easy solution would be using a sort function that doesn't use extra space. And maintain a extra variable 'a'. Every time negative and 0 entries are encountered, do a++ and move ahead in array. And compare array elements are[i] with i+1-a . In this way we basically ignore negative and zeroes and only compare +ive entries. If at any 'i' above comparison return false, I+1-a is missing
multiplying with -1 approach is also constant space and u can add a larger number than n in place of negative numbers only there'll be one extra iteration
I will say that the question should probably specify whether the array is immutable, mutable (and if changing the order is ok), or consumed via the operation. If array is immutable, or if it must be returned to its starting state after the operation, then this solution will not work since there's no way to reverse the mixing-up. If array needs only keep the same values, this solution is fine (with MEX order doesnt matter so this is ok, but say you also had queries that indexed the array, this would be an issue) if array can be consumed by the operation, there is another way which is the one I thought of - to mark an element as seen, you replace that spot with a flag like 0 or -1, and then process whatever used to be there. Before this starts you can process elements replacing any that started out as negative with something else such that it won't be confused, like turning any -1 into -2. I figured that the operation would probably either want the array to be unchanged or let it be consumed, and so while i had thought of re-ordering the array while doing some pointer jumps, decided there would be no way to reverse the operation and so didn't follow that path.
Before this i only knew that we can use the indexing trick for finding the missing and repeated number and counts of all the numbers when they are N total with no. ranging from 1 -N OR 0-N-1, Today i got something dangerous than this, following the same trick. Thanks Rachit.
Pattern: Mark visited elements in O(N) time and O(1) space. Aproaches: Negate indices of values, Or swap values into correct indices Observation: First Missing Positive lies in between 1 and n + 1. Draw test cases to observe this.
here's another similar idea, do dfs just like Rachit did, but instead of marking negative, make it equal to its index , but beforehand save prev value to be used as next index for iteration, (handle any index less than 1 or greater than n by thinking them of as end of your dfs, another end will be when value is already been made equal to its index), now we just need to search for first element which doesn't match its index
Another solution can be introducing an N bit binary number where for every positive number we switch on the ith bit from the left. Then the index of the first switched off bit in the binary number is the answer
Here some people are saying that this code fails for repeated values, but this is false. The condition - num[i] != num[correctPos] checks this thing. If you encountered a number which is not at its correct position, and the correct position is already occupied by a correct number, then this condition will not allow infinite swapping of num[i] and num[correctPos]. But if you replace the condition in while loop by i != correctPos, then in this case there will be infinite swapping in case of repeated numbers (once any one instance of the number gets placed in the correct position), because before swapping if wont check that the number num[i] that you want to swap with num[correctPos] are already same. But yes, the previous approach which has only positive numbers will fail in case there are repeated numbers. Suppose there are two 3s, then arr[3] will be multiplied by -1 two times, eventually making arr[3] positive.
The problem with this approach is that to avoid the use of additional space, we are mutating the array, and it's difficult to reverse the change once done.
Here"s my approach I will start with i=1 and check if it's in the given array if not I will increment i it goes until i is not found. time complexity will be O(n)
What if we first sort the array then start traversing the array from start and then break the loop when a[ i ] != i and the value of i will be our required answer... Is this approach correct? And if not then why not?????
Because sorting operation has a time complexity of O(n^2) in worst case and O(nlogn) in average case and we have to solve this problem in O(n). But the approach is correct if we ignore the time complexity.
@@jatinsingh6744 traversing the array will be of complexity O(n) and sorting will take O(nlogn) and eventually our final complexity will come out to be O(n). If I am wrong then please correct me.
Because sorting operation has a time complexity of O(n^2) in worst case and O(nlogn) in average case and we have to solve this problem in O(n). But the approach is correct if we ignore the time complexity.
Can’t we sort the array and run the loop from i=0 to max_ele_in_arr and use count function. If count of that element is 0 then we return that variable.. Is this approach correct???
Why not we simply replace all negative and zeros with n+1 where n is the size of the array. Effectively we are not "touching" negative and zeros at all. Is there anything wrong with this approach ?
This is an easy problem. If you have done the problem where you must reorganize all numbers in an array A such that A[i] = A[i] for all i in O(1) space O(n) time, then this is significantly more straight forward to approach.
for i in range(len(nums)+1): if i+1 in nums: continue else: return i+1 break this code for the same question on Leetcode (as provided link in your description) got accepted then why to take this complex approach.
@@gauravsonkusle3888 it got accepted because the time constraints were not that tight and you are using python as it's slow so they make the time constraints a little weak as compared to other languages.
If an array has negative numbers we can shift all negative numbers to end of the array in O(n) time. Then we proceed with the marking negative approach
Also, why not have a current and current-1 iterator (here i) and check if the difference of data at these cells is greater than 1 and hence return the required value. Also, if for the current approach what if there are duplicate elements in the array?
Hi Rachit, if we maintain smallest and second smallest number while we traverse through the array,then we can find out the missing smallest positive number right which basically lies in between these two numbers
How about this approach o(n) time, o(1) space.. 1) Use quicksort algorithm to swap all -ve numbers to the beginning of the array 2) Now from position x to n, we have only +ve numbers 3) Now we can use the +/- technique to denote which positive integers are present in the array, by making that index -ve
We can do it using multiplication by -1 technique also. We just need to make all the numbers less than equal to 0, some invalid number like n+1 , or INT_MAX.
How about multiplying a number with a large prime number instead of -1 for array which can contain negative numbers..and then for checking which is missing number simply mod all the elements of array by that prime number.will this work?
Does this work? What if we check the array once for '1', if it doesn't have a '1' we output the answer as one, if it has a '1' we set all negative numbers to 1 and proceed with the negative marking algorithm?
Thanks for the new approach Rachit. I was not able to get how time complexity is still O(N). I understood the whole solution and indeed it was very well explained. Thanks Rachit
where you are doing in O(N)? You are iterating over all the elements and then swapping untill the number has the valid position so where is the timecomplexity O(N) follows? I didn't understand that.Please anyone has idea about this please let me know.
bdw good work bro..you're my inspiration. Please make a video series in DP how to figure out that what problem goes under dp. If it is possible then make a series.
Didn't understand in GFG, then I suddenly remember Rachit has uploaded this, I saw in the notification a few days back but didn't watch at that time. and I got it .
the same question they asked me in round 2 of sde 2. I gave an answer of O(N), then suddenly they wanted an answer without extra spaces!! I stucked forever there. 😶
So you got accepted or not ? XD
@@krsingh.shubham In this particular round, they was ok with me, I got rejected from Managerial round
@@sjchat aah !. good luck other interviews.🤞
@@krsingh.shubham thanks dude. ❤️
@@sjchat That's great. At least you reached the managerial round. I had my heart in my mouth when you said you couldn't come up with constant space solution.
I guess now i am able to solve leetcode's first missing positive hard question. No resource did this easy explanation. Thanks Rachit.
thats true. but i wanna know how long do they take to design and make this algorithm work.
I was asked this as my first question on my Round 1 of Amazon interview and I gave the O(max(element)) soln and he was satisfied. He asked me to optimize it further but was not able to do it. Thanks Rachit for doing such a wonderful solution.
We can apply the first approach on -ve elements as well by using shifting. shift all -ve values to front and then apply the 1st approach you mentioned for +ve numbers in array.
That will change runtime to O(n^2).
@@rohankrishnaullas6705 O(n) + O(m) m-> number of positive elements m
@@HarshGangwar consider an array of size n with fist n/2 elements positive and last n/2 elements negative. So to move all the last n/2 elements to front ,each of the last n/2 elements will have to traverse a distance of n/2 i.e O(n/2 * n/2) = O(n^2).
Eg : [1,2,3,4....500,-1,-2,-3...-500]
To move -1 to pos 0 takes n/2 ops and similarly for all rem negative elements.
@@rohankrishnaullas6705 the approach you are explaining is shifting. You can just swap every negative element you encounter to the jth index(initially 0) and then increment the value of j. This will be O(n)
Instead, mark negative elements can be changed to zero and ignore them in the next traversal!
for anyone looking for a bit simpler code, with the same idea
while(i < A.length){
if(A[i] == i+1 || A[i] A.length) i++;
else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
else i++;
}
i = 0;
while(i < A.length && A[i] == i+1) i++;
return i+1;
Dude, the whole animation and production is amazing along with the explanation.
The fact that answer is
This question was really cool. Amazing solution !
I just changed all negative number to n+1, but thanks to You I got another way to think about the solution. Thanks 😊
yes your approach is more intuitive
alll negative and zero also then first method also works
This was asked in samsung and VMware interview too
This solution was amazing. I saw a question where the array was sorted and we had to find the mex in log(n) time. I guess we can simply find the point where difference between index and the number is 1 using binary search
Yes, we can use binary search. I think it can be done like this -
Lets set l = 1 and r = n+1 for binary search. Then the number we predict as our ans will be mid. Then if the index of number is having number larger than it then our ans might be this mid and since we need to minimize we shift r towards mid. If the index equals the value then we should move our l towards mid. During the process we can keep track of minimum and get our ans
In addition to the first approach, we can change the 0s and negatives to Array Size + 1 and then iterate in the array to make the postive numbers negative. After that, we can return the index (i+1 actually) of the first negative number found.
When I started the video and think of the solution I got the XOR solution but then you threw the O(1) limit then I got stuck😅😅, As always Amazing video Rachit 😎🔥🔥
For the case of all +ve numbers, if the array had repetitions say, arr =[1, 1], arr will become [-1,1] first and then [1,1] on multiplying by -1. We will get an answer as 1 when it should be 2. So multiplying by -1 should happen only when the element at that index is positive.
yes, u r right about that!!
The same code in python runs timeout in interviewbit
That's why Python isn't preferred for CP ... owing to more time it takes
@@utkarshagarwal8390 no...there is a problem in this logic..it will fail for duplicates
To solve this segeregate the negative from positives ..keep your negativity to left part of array and then apply the first algo taught in this video on the positive part
@@PhoenixRisingFromAshes471 r u sure? Coz there is a condition in while loop to check that?
As the array can be modified then all the "non positive" numbers can be replaced with N+1 (N=size of the array). Then I think the previous approach will work.
we can make all -ve and > N numbers as 0 and rest all numbers occurrence will be marked as 1 in that index. and the first index which has 0 that is the missing
When I was watching this video I also came up with an approach that if size is N and there is no copy then
at max N+1 could be the mex
so we can store the sum of N numbers let tmp = (N+1)*(N)/2
and now iterate over the entire array if the value is less than N and greater then 0 decrease the value of tmp with that value ,
after iteration if the tmp is 0 ans should be N+1 else ans will be tmp
To avoid failure of your O(1) space approach we can change all the negatives to 1 before applying that method. That would definitely work
Not to 1, but probably n+1.
Best explanation ever on this question. Thanks a lot.
The while loop logic didn't cross my mind while implementation , now I got it . Thanks a lot.
why while loop is used ???
This question is also done as
Int k=1
For (int I=0;I
Will it goes to o(n ^ 2) in the worst case?
One traversal for o(n) and inside that we are doing swap which could be for n -1 elements?
Example array = [3, 4, 2, 9]
at 10:50 you say same
That's exactly what I am thinking. Can anyone clear.
Great explanation, but fails for the array with repeated numbers, for ex. [1, 3, 6, 4, 1, -2]. As it swaps with the element at correct position, it enters infinite loop on the 2nd occurrence of 1.
exactly!! did u find which solution would be correct for those situations?
What if the elements in given array are not distinct...like there are duplicates. For example the given array is : 1,3,3,6,7,8,9,9,10.
I think same code will work
It will work
If I sort the array in ascending order like 1,3,4,7. Then iterate to check the difference between consecutive digits(3-1,4-3,7-4 etc). For the first difference that is >1, I add 1 to the left hand side value(1+1), to get the smallest number.
Yes, Its good answer but What about if array has duplicate numbers.
Exactly that what i was thinking...it will surely fail for duplicates.........to solve this segregate the positive and negative numbers (keep all the negatives to left of positives)and then apply the first algo on the positive part
Before swapping we will check if the index already has a correct value or not, if not then we will swap or else we will continue.
What if the array is 3 1 3 4 your swapping logic will stuck in loop swapping 3 and 3 repeatedly?
you can write a logic that breaks out of a loop when value of element doesnot change after swapping
An easy solution would be using a sort function that doesn't use extra space. And maintain a extra variable 'a'. Every time negative and 0 entries are encountered, do a++ and move ahead in array. And compare array elements are[i] with i+1-a . In this way we basically ignore negative and zeroes and only compare +ive entries. If at any 'i' above comparison return false, I+1-a is missing
Only problem is time complexity, which will be O( n log n). Pretty sure you'll be asked to optimise it.
multiplying with -1 approach is also constant space and u can add a larger number than n in place of negative numbers only there'll be one extra iteration
Oh my god. Hats off to the person who got with this solution. As a fellow developer the logic is amazing
it brought my confidence down to 0 :'( c
@@ruralbaby1921 It's alright. We can always learn what we don't know.
In this solution, we also need to make sure to break the loop if element at the current index remains the same after an iteration.
Thanks Rachith Bhayya . I was really shocked why geeks was using this technique.... But u made me understand it very well♥️♥️
I will say that the question should probably specify whether the array is immutable, mutable (and if changing the order is ok), or consumed via the operation.
If array is immutable, or if it must be returned to its starting state after the operation, then this solution will not work since there's no way to reverse the mixing-up.
If array needs only keep the same values, this solution is fine (with MEX order doesnt matter so this is ok, but say you also had queries that indexed the array, this would be an issue)
if array can be consumed by the operation, there is another way which is the one I thought of - to mark an element as seen, you replace that spot with a flag like 0 or -1, and then process whatever used to be there. Before this starts you can process elements replacing any that started out as negative with something else such that it won't be confused, like turning any -1 into -2.
I figured that the operation would probably either want the array to be unchanged or let it be consumed, and so while i had thought of re-ordering the array while doing some pointer jumps, decided there would be no way to reverse the operation and so didn't follow that path.
sir pls tell when the array will contain 0, how do we apply this method to find the missing no
The algorithm works for 0 also. Do check it yourself
We could have used Negative array indexing. O(n) TC and SC is O(1)
This is best explanation of this question in the whole world. Thanks Rachit.
Before this i only knew that we can use the indexing trick for finding the missing and repeated number and counts of all the numbers when they are N total with no. ranging from 1 -N OR 0-N-1, Today i got something dangerous than this, following the same trick. Thanks Rachit.
This is the simplest and beautiful solution.
Thanks man!
This is the bucketing technique.Thanks again man!
I think the second approach can be extended for negative no. too. Instead of multiplying by -1 we can subtract/add infinite to the value
@utkrash Gupta can u send the code buddy! n explaintion
thanks bhaiya for this solution what i couldn't do understand in 12 hr you made it understand in 14 min.god bless u
Pattern: Mark visited elements in O(N) time and O(1) space.
Aproaches: Negate indices of values, Or swap values into correct indices
Observation: First Missing Positive lies in between 1 and n + 1. Draw test cases to observe this.
here's another similar idea, do dfs just like Rachit did, but instead of marking negative, make it equal to its index , but beforehand save prev value to be used as next index for iteration, (handle any index less than 1 or greater than n by thinking them of as end of your dfs, another end will be when value is already been made equal to its index), now we just need to search for first element which doesn't match its index
my bad, didnt see ahead in the video before commenting, i just came here after solving it on leetcode , too much time taken
sorry for this long thread, you can not simply swap elements, i did try that, fails for cases like [1, 1] where swapping will create infinite loops
Another solution can be introducing an N bit binary number where for every positive number we switch on the ith bit from the left. Then the index of the first switched off bit in the binary number is the answer
What if there is a number like 1 lakh. You will take a 1 lakh bit binary number for it?
Instead of negating the number. Convert the number to string. So on which index the number isn't a string is the least missing number
Here some people are saying that this code fails for repeated values, but this is false. The condition - num[i] != num[correctPos] checks this thing. If you encountered a number which is not at its correct position, and the correct position is already occupied by a correct number, then this condition will not allow infinite swapping of num[i] and num[correctPos].
But if you replace the condition in while loop by i != correctPos, then in this case there will be infinite swapping in case of repeated numbers (once any one instance of the number gets placed in the correct position), because before swapping if wont check that the number num[i] that you want to swap with num[correctPos] are already same.
But yes, the previous approach which has only positive numbers will fail in case there are repeated numbers. Suppose there are two 3s, then arr[3] will be multiplied by -1 two times, eventually making arr[3] positive.
Amazing question ! 👌 And amazing solution ! 💯
Rachit I think your solution for the negative number may run in O(n2) in worst case scenario. Please correct me if I am wrong.
The problem with this approach is that to avoid the use of additional space, we are mutating the array, and it's difficult to reverse the change once done.
We can also use unordered_set and insert all the elements into it. Then iterate from 1 to N+1 and return which is missing
That's O(N) space!
Here"s my approach I will start with i=1 and check if it's in the given array if not I will increment i it goes until i is not found. time complexity will be O(n)
Nope, you are neglecting the time taken by the search operation which is O(n). So O(n*n) overall.
What if we first sort the array then start traversing the array from start and then break the loop when a[ i ] != i and the value of i will be our required answer...
Is this approach correct?
And if not then why not?????
Because sorting operation has a time complexity of O(n^2) in worst case and O(nlogn) in average case and we have to solve this problem in O(n). But the approach is correct if we ignore the time complexity.
@@amansingh9835 we could use merge sort that has complexity of nlogn in worst case
@@adityashukla7562 clearly in the video it is described that we need to do it in time complexity of O(n)
@@jatinsingh6744 traversing the array will be of complexity O(n) and sorting will take O(nlogn) and eventually our final complexity will come out to be O(n).
If I am wrong then please correct me.
@@adityashukla7562 bro nlogn > n , so sorting itself will take O( nlogn ) time,
A very good question explained in simplest way.Thank you sir...🙌
What about doing an in-place sorting Algorithm like quick sort and then iterate over the array to find the result......would this work???
Because sorting operation has a time complexity of O(n^2) in worst case and O(nlogn) in average case and we have to solve this problem in O(n). But the approach is correct if we ignore the time complexity.
@@amansingh9835 oo.... didn't thought of that😅😬
Can’t we sort the array and run the loop from i=0 to max_ele_in_arr and use count function. If count of that element is 0 then we return that variable.. Is this approach correct???
will it work for repeating integer values in the array (1,2,2,3,3,-2,-4,-5)
or firstly we have to remove -ve and repeated elements from the array.
you can write a logic that breaks out of a loop when value of element doesnot change after swapping
thank you for this simple and clear explanation brother
if numbers are same then we need to small change in code that if(A[i]==A[A[i]-1]) break;
Why not we simply replace all negative and zeros with n+1 where n is the size of the array. Effectively we are not "touching" negative and zeros at all. Is there anything wrong with this approach ?
This is an easy problem. If you have done the problem where you must reorganize all numbers in an array A such that A[i] = A[i] for all i in O(1) space O(n) time, then this is significantly more straight forward to approach.
for i in range(len(nums)+1):
if i+1 in nums:
continue
else:
return i+1
break
this code for the same question on Leetcode (as provided link in your description) got accepted then why to take this complex approach.
can someone respond to this.. i have the same doubt... is it possible that there's a problem with leetcode?
its a O(n^2) approach because of this statement " if i+1 in nums: " , "in" is O(n) operation as you are searching the whole array.
@@Yeager098 yeah..thought the same... but it got accepted on leetcode...why? how can that happen? is there something wrong with leetcode?
@@gauravsonkusle3888 it got accepted because the time constraints were not that tight and you are using python as it's slow so they make the time constraints a little weak as compared to other languages.
@@Yeager098 okay... got ur point...thanks for replying bro
another solution would be :
1) iterate through the array and replace the values which are
What if the array contains duplicates ?
Bhaiya u made it so simple now it's not looking hard one
If an array has negative numbers we can shift all negative numbers to end of the array in O(n) time. Then we proceed with the marking negative approach
in the approach using swaps how did you handle duplicates?
Very helpful tip. How do you come up with such solutions, experience in competitive programming or some invisible tutorials??
What software is used to make these sort of explaination videos and small animations ?
Edits the video and gives voice to it
@@akashp4863 bruh
How would this work if the array has numbers greater than indices? eg. [300,400,700,100].
Also, why not have a current and current-1 iterator (here i) and check if the difference of data at these cells is greater than 1 and hence return the required value.
Also, if for the current approach what if there are duplicate elements in the array?
what if numbers are repeating like [1 , 1] then the while loop will not stop.
check the second condition in while loop of code implementation. if the current value is equal to the value we are going to swap with we break out.
I think first approach still work if intially we separate a negative no. and positive no. and did same with start from first positive integer.
Hi Rachit,
if we maintain smallest and second smallest number while we traverse through the array,then we can find out the missing smallest positive number right which basically lies in between these two numbers
1,2,3,6
How will your approach work in this?
we can handel -ve value and zro by converting them to n+1 .
How about this approach o(n) time, o(1) space.. 1) Use quicksort algorithm to swap all -ve numbers to the beginning of the array 2) Now from position x to n, we have only +ve numbers 3) Now we can use the +/- technique to denote which positive integers are present in the array, by making that index -ve
how come last solution is not having time complexity of (N2)???
Sir we can also change the value of negative numbers or zeros to a number greater then n and then apply the first method. Correct me if I am wrong 😁.
How about moving from 0 to length of array and searching for first missing element? I'm new to time-space analysis please spare me if I'm wrong.
In the second approach we can use -INF
Wouldn't the first approach you gave not work either if there existed negative elements in the array?
But this code will not work if elements of array are similar, while loop will run indefinitely.
How do I solve this question if the input array has repeated values e.g. [1, 1, 7, 3, 4]
Will it be possible to cover a little more formal proof for correctness, for greedy ones please?
Rachit bhaiya what if an array containing duplicate values too?
Too simple and great explanation bro
We can do it using multiplication by -1 technique also. We just need to make all the numbers less than equal to 0, some invalid number like n+1 , or INT_MAX.
Yeah that should work too! Good finding.
Jain Sahab , Tusi Chha Gaye .. Loved the explanation and Logic
Cant we run a loop and replace all negative numbers with n+1
How about multiplying a number with a large prime number instead of -1 for array which can contain negative numbers..and then for checking which is missing number simply mod all the elements of array by that prime number.will this work?
Does this work?
What if we check the array once for '1', if it doesn't have a '1' we output the answer as one, if it has a '1' we set all negative numbers to 1 and proceed with the negative marking algorithm?
Thanks for the new approach Rachit. I was not able to get how time complexity is still O(N). I understood the whole solution and indeed it was very well explained.
Thanks Rachit
a while loop within a for loop, wont it give a time complexity of O(N^2)??
where you are doing in O(N)? You are iterating over all the elements and then swapping untill the number has the valid position so where is the timecomplexity O(N) follows? I didn't understand that.Please anyone has idea about this please let me know.
I did mention in the video about this aspect. Probably watch again.
bdw good work bro..you're my inspiration. Please make a video series in DP how to figure out that what problem goes under dp. If it is possible then make a series.
Didn't understand in GFG, then I suddenly remember Rachit has uploaded this, I saw in the notification a few days back but didn't watch at that time. and I got it .
This wouldn't work if the input has duplicate?
What if there is zero in the array. How will you get the correct position then ?🤔
What if we have duplicates in array (multiple occurrence of a number) will this approach work properly ?
What if you just deleted the number at ith index instead of swapping? Then won't index corresponding to the first non-null number be the ans?
do you think that they will ask questions like these in the first round
of interview?