because first you are making all the elements in range , then you mark negative the element where it should have been present ,all the negative elements in the end will represent the found numbers and whichever is not marked from the left will be our answer.
Think of its as , first you are searching for 1 if it is present make the flag equal to true and if any time you see a number which is less than or equal to zero or the number is greater than the size of array then it is of no use for us, because we don't want any negative numbers and if the array length is n and if there are all numbers from 1 to n in this , it means n+1 is the smallest missing positive number and that is why if any number in the array is greater than size of the array then it is of no use for us, then why we are mapping, because we know now all the numbers in the array now in the range of 1 to n, we know hashing concepts to search for a element faster i.e, in O(1), why we are making nums[index - 1] as negative ? why not nums[index] ? The answer is because we want only smallest positive number , smallest positive number starts from 1, if you encounter 1, how to use the indexes for faster access of elements? we know that zero is not present in the array now, so we can 0 index for that if 1 is present or not and same 1 index we can use if 2 is present or not, i.e, we are saying if n is present, then index n-1 must be negative, that is why we are marking nums[index-1] as negative and also you can think if the length of array is n and if n is present in the array , then how can you identify if n is present because n index is not present in array of size n, that is why we are using i-1 indexing for checking if i element is present, then now you will finally find the missing number by again traversing the updated array, if the index is negative it means index+1 is present in the array and if any element you encounter which is greater than 0 , then it means the index in which this element is present, it means index+1 is not present in the array, because if it was present, then nums[index-1] must had been negative, if you searched all the array , you can't find a single positive element in the array , it means n+1 is not present in the array.
We havent used extra space. Extra space means, with the increase of input size, your extra space should increase. In our case, we have a constant variable, i.e even if n=1000, there will be one boolean and if n==1, there will be one boolean.
Yes. We will do in-place swapping in the array such that every index has value same as the index+1 and ignore negative and greater than n(array.length)values. Then the first index which doesn't have same value as the index+1 will give us the answer .Answer will be index+1.
array length is 4 and numbers in range 4 so all good. and in first loop nothing to mark as 1 since all in range and boolean for 1 found is also true. Then iterate. first element is 3 so 3-1 = 2 but at index 2 value is already negative so no update required, then value is 4 so 4-1=3 make 3rd index value as -1, then -1 take absolute of it which is 1 so 1-1=0 make 0th index value as negative then again 1 so 1-1 is 0 and 0th index value is already negative so no change. Then in next iteration we got index 1 which is having +ve value so answer will be 1+1 = 2 which is missing
After watching lot of youtube videos and reading articles finally my search ended here.
thanku sir..
how to think this type of appraoch
very well explained!
Samay Raina teaching Java
Nice
🤣🤣🤣🤣🤣
if there is any pepcoding video available then i will definitely watch that .
approach is good but work on how to teach to make all understand
very good explanation
thank you sireesh sir
great sir. thanking for making the explanation so simple
Great Sir, You explained it very well...
so nice
Mast approach tha bhai. Thanks a lot.
but why it is working??? I'm not clear about it..
because first you are making all the elements in range , then you mark negative the element where it should have been present ,all the negative elements in the end will represent the found numbers and whichever is not marked from the left will be our answer.
Awesome approach sir.. Maza agya
stay motivated and keep learning :)
Why this approach worked?? I mean if I give this solution to someone else then how can I prove this solution will always work?
Think of its as , first you are searching for 1 if it is present make the flag equal to true and if any time you see a number which is less than or equal to zero or the number is greater than the size of array then it is of no use for us, because we don't want any negative numbers and if the array length is n and if there are all numbers from 1 to n in this , it means n+1 is the smallest missing positive number and that is why if any number in the array is greater than size of the array then it is of no use for us, then why we are mapping, because we know now all the numbers in the array now in the range of 1 to n, we know hashing concepts to search for a element faster i.e, in O(1), why we are making nums[index - 1] as negative ? why not nums[index] ? The answer is because we want only smallest positive number , smallest positive number starts from 1, if you encounter 1, how to use the indexes for faster access of elements? we know that zero is not present in the array now, so we can 0 index for that if 1 is present or not and same 1 index we can use if 2 is present or not, i.e, we are saying if n is present, then index n-1 must be negative, that is why we are marking nums[index-1] as negative and also you can think if the length of array is n and if n is present in the array , then how can you identify if n is present because n index is not present in array of size n, that is why we are using i-1 indexing for checking if i element is present, then now you will finally find the missing number by again traversing the updated array, if the index is negative it means index+1 is present in the array and if any element you encounter which is greater than 0 , then it means the index in which this element is present, it means index+1 is not present in the array, because if it was present, then nums[index-1] must had been negative, if you searched all the array , you can't find a single positive element in the array , it means n+1 is not present in the array.
we can mark out of range 0 and while map if arr[i]==0 continue;
else arr[arr[i]-1]=-ve
but cant make it negative
Bhai we can't use extra space Boolean array
We havent used extra space. Extra space means, with the increase of input size, your extra space should increase. In our case, we have a constant variable, i.e even if n=1000, there will be one boolean and if n==1, there will be one boolean.
bro wo variable h naki array
Good explaination
approach clear nhi hai
aur why to pata hi nhi chala
Is there any solution without modifying the input in time O(n) and space O(1)?
Yes. We will do in-place swapping in the array such that every index has value same as the index+1 and ignore negative and greater than n(array.length)values. Then the first index which doesn't have same value as the index+1 will give us the answer .Answer will be index+1.
class Solution {
public: int firstMissingPositive(vector A) {
int n = A.size();
for(int i = 0; i < n; ++ i) {
while(A[i] >= 1 && A[i]
@@Phantomm2019 But wouldn't that actually mean modifying the input array?
@@heya2k198 yess it will modify the array....I didn't notice the requirement of not modifying array😅
Not working for the test case [3,4,-1,1]
array length is 4 and numbers in range 4 so all good. and in first loop nothing to mark as 1 since all in range and boolean for 1 found is also true. Then iterate. first element is 3 so 3-1 = 2 but at index 2 value is already negative so no update required, then value is 4 so 4-1=3 make 3rd index value as -1, then -1 take absolute of it which is 1 so 1-1=0 make 0th index value as negative then again 1 so 1-1 is 0 and 0th index value is already negative so no change. Then in next iteration we got index 1 which is having +ve value so answer will be 1+1 = 2 which is missing
Awesome
wow kya approach hai
I have dry ran .This will not work for 2
0 1
N=2 I/p 0 1
if(arr[i]>arr.length || arr[i] == 0) {
arr[i] = 1;
}
2nd method is wrong because it can contain duplicate or more than one value
Niceee❤
Sir code ka font toda increase kr do
Acknowledged for next time
And use white background please