🔴 Amazon Interview Question - Missing Smallest Positive Number | Free Giveaway 🎁
Vložit
- čas přidán 26. 07. 2024
- ✅New CZcams Account - Developer Bhaiya 👉🏻bit.ly/developer-bhaiya-youtube 👀rachitiitr.com - My Personal Portfolio and things I recommend for Coding Interviews.
Rachit, an ex-Software Engineer@Microsoft discuss in detail the initial ideas, the correct strategy, the code and time/space complexity analysis of a Greedy problem on Arrays.
Problem Link (for you to practise): leetcode.com/problems/first-m...
Github Code in Python (Star the repository): github.com/rachitiitr/DataStr...
Github Code in C++ (Star the repository): github.com/rachitiitr/DataStr...
✅ Complete Playlist "FANG Coding Interviews with Animated Solutions" 👉🏻 • Amazon Interview Quest...
✅ 𝗘𝗱𝘂𝗰𝗮𝘁𝗶𝘃𝗲.𝗶𝗼 [10% OFF for First 70 Users] 👉🏻educative.io/rachit
⚠️Rules for 3-month giveaway to Educative website
👉🏻Follow @rachitiitr on Instagram
👉🏻Comment below on this CZcams video, "interested @your_instagram_id_here"
👉🏻A random winner from comment would be decided in 4 weeks
👉🏻The Winner gets contacted on their Instagram with the voucher for giveaway
𝗜𝗡𝗧𝗘𝗥𝗩𝗜𝗘𝗪 𝗣𝗥𝗘𝗣 𝗣𝗥𝗢𝗗𝗨𝗖𝗧𝗦
✅ 𝗔𝗹𝗴𝗼𝗘𝘅𝗽𝗲𝗿𝘁 [15% OFF coupon "rachit"] 👉🏻algoexpert.io/rachit
✅ 𝗦𝘆𝘀𝘁𝗲𝗺 𝗗𝗲𝘀𝗶𝗴𝗻 [Discount for Indian audience] 👉🏻bit.ly/design-rachit
✅𝗘𝗱𝘂𝗰𝗮𝘁𝗶𝘃𝗲.𝗶𝗼 [10% OFF for First 70 Users] 👉🏻educative.io/rachit
✅ 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴 𝗕𝗼𝗼𝗸𝘀 [Amazon Affiliate] 👉🏻amazon.in/shop/rachitjain
SUBSCRIBE AND HIT BELL ICON TO CHECK MORE OF MY CONTENT
czcams.com/users/RachitJain?sub_con...
𝗜𝗠𝗣𝗢𝗥𝗧𝗔𝗡𝗧 𝗣𝗟𝗔𝗬𝗟𝗜𝗦𝗧𝗦
✅ 𝗖𝗼𝗱𝗶𝗻𝗴 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗟𝗲𝗰𝘁𝘂𝗿𝗲𝘀 👉🏻 • Day 3: Coding Intervie...
✅ 𝗚𝗿𝗮𝗽𝗵 𝗧𝗵𝗲𝗼𝗿𝘆 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • Graph Theory and Algor...
✅ 𝗖++ 𝗦𝗧𝗟 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • The Best Demo on C++ S...
✅ 𝗠𝘆 𝗣𝗲𝗿𝘀𝗼𝗻𝗮𝗹 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗘𝘅𝗽𝗲𝗿𝗶𝗲𝗻𝗰𝗲𝘀 👉🏻 • Uber SDE II Interview ...
✅𝗣𝗿𝗼𝗱𝘂𝗰𝘁𝗶𝘃𝗶𝘁𝘆 𝗧𝗶𝗽𝘀 𝗣𝗹𝗮𝘆𝗹𝗶𝘀𝘁 👉🏻 • Uber SDE II Interview ...
✅𝗟𝗶𝗳𝗲 𝗟𝗲𝘀𝘀𝗼𝗻𝘀 & 𝗠𝗲𝗻𝘁𝗼𝗿𝘀𝗵𝗶𝗽 👉🏻 • Why I Chose To Become ...
𝗦𝗢𝗖𝗜𝗔𝗟 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦
✅rachitiitr.com
✅ / rachitiitr
✅ / rachitiitr
✅ AlgorithmsWithRachitJain
✅ / rachitiitr
𝗣𝗥𝗢𝗚𝗥𝗔𝗠𝗠𝗜𝗡𝗚 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦
✅ Github ► github.com/rachitiitr/DataStr...
✅ Programming Blog ► rachitiitr.blogspot.com
✅ CodeForces ► www.codeforces.com/profile/rac...
✅ CodeChef ► www.codechef.com/users/rachitiitr
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.
This question was really cool. Amazing 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.
The fact that answer is
Dude, the whole animation and production is amazing along with the explanation.
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;
This was asked in samsung and VMware interview too
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.
The while loop logic didn't cross my mind while implementation , now I got it . Thanks a lot.
why while loop is used ???
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
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 😎🔥🔥
This is the simplest and beautiful solution.
Thanks man!
Amazing question ! 👌 And amazing solution ! 💯
A very good question explained in simplest way.Thank you sir...🙌
Thanks Rachith Bhayya . I was really shocked why geeks was using this technique.... But u made me understand it very well♥️♥️
Best explanation ever on this question. Thanks a lot.
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
This is the bucketing technique.Thanks again man!
love your animated vids bhaiyya, it's really fun watching them!!!
This is best explanation of this question in the whole world. Thanks Rachit.
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
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 .
thanks bhaiya for this solution what i couldn't do understand in 12 hr you made it understand in 14 min.god bless u
thank you for this simple and clear explanation brother
Jain Sahab , Tusi Chha Gaye .. Loved the explanation and Logic
Bhaiya u made it so simple now it's not looking hard one
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
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.
Super, thanks for the pristine tutorial
Loved the way of teaching!!
We could have used Negative array indexing. O(n) TC and SC is O(1)
Too simple and great explanation bro
Hey Rachit,
Nice explanation. Thanks 🙂
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.
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.
Very helpful tip. How do you come up with such solutions, experience in competitive programming or some invisible tutorials??
Good explanation.Thank You
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
Thanks a lot! Amazing solution!
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.
thanks a lot brother to make tricky question easy
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.
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
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
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.
Understood well, thanks for the help ,commeting on the video for better reach, cuz that's the only thing i could do for now😇
This question is also done as
Int k=1
For (int I=0;I
Rachit Bhaiya!!! can you please make more animated videos like this of most asked interview quetions these are really very helpfull....!!!!
another solution would be :
1) iterate through the array and replace the values which are
Amazing explanation !!
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.
In the second approach we can use -INF
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.
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.
This exact approach gave me tle
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?
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?
Amazing solution sir
I was able to crack the solution after watching half part of the video, really excited to watch the next half of the video.
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.
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.
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.
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
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.
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?
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???
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
we can handel -ve value and zro by converting them to n+1 .
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
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
Cool !!
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 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?
if numbers are same then we need to small change in code that if(A[i]==A[A[i]-1]) break;
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 😁.
awesome explination
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?
Can such problems even be solved? These are just solutions that you either know, or you don't. How are these interview questions anyway? Crazy.
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!
Nice explanation
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.
Will it be possible to cover a little more formal proof for correctness, for greedy ones please?
The time complexity is O(n^2).
Many have just copy pasted your code on leetcode :)
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
@iknowsomedeeplearning .... Also connected with you in LinkedIn ... Really need this giveaway ..
Best explanation
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.
Yesterday I solve this question in geekforgeeks...
I can say this is very good question
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
why are we returning n+1,f we are not getting any missing number
6:01 we you said paise the video and think it.
I got a youtube add of algoexpert 🤣🤣
whoa what a solution man
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.
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 ?
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 have duplicates in array (multiple occurrence of a number) will this approach work properly ?