First Missing Positive | Leetcode 41(Hard-tag) Solution in Hindi
Vložit
- čas přidán 27. 07. 2024
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. 1. Given an unsorted integer array 'arr'.
2. Find the smallest missing positive integer.
Note : You must implement an algorithm that runs in O(n) time and uses constant extra space.
Topic: #Arrays, #Chaining
Used #DataStructure: #Arrays
#TimeComplexity: O(n)
#SpaceComplexity: O(1)
---------------------------------------------------------------
For detailed information and other exercises, VISIT: www.pepcoding.com
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
----------------------------------------------------------------
#arrays, #strings, #pepcoding, #leetcode, #ArraysAndStrings, #FirstMissingPositive, #Leetcode41, #41Leetcode
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/
Have a look at our result: www.pepcoding.com/placements
Follow us on our CZcams page: / pepcoding
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Follow us on Pinterest: / _created
Follow us on Twitter: home
.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer
After watching lot of youtube videos and reading articles finally my search ended here.
thanku sir..
how to think this type of appraoch
Samay Raina teaching Java
Nice
🤣🤣🤣🤣🤣
Mast approach tha bhai. Thanks a lot.
Great Sir, You explained it very well...
great sir. thanking for making the explanation so simple
approach is good but work on how to teach to make all understand
if there is any pepcoding video available then i will definitely watch that .
very well explained!
wow kya approach hai
Awesome approach sir.. Maza agya
stay motivated and keep learning :)
thank you sireesh sir
Good explaination
very good explanation
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.
Niceee❤
2nd method is wrong because it can contain duplicate or more than one value
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
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
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😅
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.
Awesome
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
approach clear nhi hai
aur why to pata hi nhi chala
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;
}
Sir code ka font toda increase kr do
Acknowledged for next time
And use white background please