Quite a smart way to map the value itself to the respective index position (value - 1) in the nums array since the the array will always contain the numbers ranging from 1 to n. I couldn't figure it out without using a hash set. Thanks for the solution.
Should we assume we can use the input array as extra memory when we face this kind of problem in an interview? I thought this might be a bad practice in real world scenarios.
It's prob worth confirming with your interviewer before you start coding it. Fwiw it would be easy to revert the changes we made to the array if the interviewer prompted us to.
Your coding interview is not supposed to reflect how you code in a normal environment, it’s meant to show your mentality. This problem in particular presents your ability to be resourceful
i think this is a mistake on their behalf but arent you making an extra array res that in the worst case gonna be of length O(n/2) which simplifies to O(n) ?, also here's a problem that is basically the same as this one for people who wanna solve it (yesterday's problem) : 287. Find the Duplicate Number
if you use a different property, you can do it in true O(1) space complexity by returning the input array after modification this involves adding n+1 to elements when visited and using %(n+1) to check further indexes u can then test for all values greater than 2(n+1) and change them to their index values (note the 1-indexing) and remove from list in O(1) for at worst n items, as relative order doesnt matter and thus removal can be done by swapping to end of array i think this approach adheres to the spirit of the question much better :)
This is epic. I can never come up with this idea on my own. Despite I use collections.Counter and list comprehension to reach to beat-85% runtime speed, your idea is still brilliant.
already solve it, with my own intuition of cycle sort but I feel its not very efficient although it was O(n) time, now I'm here to get more efficient solution
There’s actually a constant space and constant *time* solution. Basically you choose a random index and add that to the result array, then return immediately. The downside is that it has an accuracy complexity of P(1/N^2) avg case and P(0) worst case, however when it works it’s da best!
I’d solve this with the hare and tortoise algorithm, mutating the base array to keep a Constant space is hacky for me (and would not to be possible in functional langs), pretty straightforward solution tho
Alternative solution: you walk through the array, if a[i] - 1 = i, continue. If a[a[i] - 1] !=a[i], you swap them. Keep swapping until you either unravel the whole cycle, or you find a duplicate. If you find a duplicate, you can mark it and continue. Very similar, performance characteristics I believe.
Thanks for the video. Do you sometimes skip daily questions even if you didn't solve them? Because I don't remember exactly which dates (february or march) but I looked for the daily questions but I couldn't find them.
generally speaking if ain't done in-place it's pretty much O(n) extra memory regardless. And can't think of solution less then O(nlogn) time which could swap out dupes somehow.
Hi nice solution does this logic work when we have a test case like this n =4 and nums = [3,3,3,3] this would return res =[3,3] and we would have duplicates in the result array so we may need to add a condition to check if that number is already present in the result list? Thanks in advance @neetcodeio
Well when I saw the thumbnail of the video, I went straight to the leetcode and tried solving the problem myself . So thing that was confusing me was that we have to use constant extra space otherwise we could use a HashSet and store all the elements and then check if any element is present twice we push that to the result array or we could iterate through the array twice but that would be O(n2). So then I thought of the Dictionary(Key-Value) . So we can simply generate a frequency map using a for/foreach loop and keep track of the elements frequencies using a dictionary and when the frequency of an element equal 2 we push that to the result. So sine dictionary is not dependent on input array it's constance space and we are iterating through the array once so it's O(n). I'm getting better though xD.
That's not constant space. This is just the hash set solution with minor modifications. The dictionary is totally dependent on the input array since you add all values in the input array to the dictionary.
This assumes mutability of the input data. You are still using O(n) space since you are "stealing" one bit from each array position to use as a flag and you need n of them. Its a clever solution to a problem that has a very badly specified question.
can you do "126. Word Ladder II"? You have done 127, but this one is more specific and it can easily go to TLE. I cannot find a clear video solution for 127.
Hey bro , i have a question to you , in today's market 40% jobs are on tool base d technologies like devops enginner , RPA developer , etccc . So Top product based companies work on these tools and sell these ools like microsodt developed power automate for RPA engineers . Sales force created muel soft for API developement . So it is good to go for working on these tool based techh orgo for DSA and work on creation of these technn. I request you to make a video these because , i see you have digging knowledge in Technology . Its a request .
True but yesterday's question specifically asked not to change the input array itself. So Floyd's Tortoise and Hare algorithm might be the only optimal solution based on yesterday's constraints
Would it also be O(1) if we remove duplicate from set after finding it? function findDuplicates(nums: number[]): number[] { const res = [] const set = new Set() for (const num of nums) { if (!set.has(num)) { set.add(num) } else { set.delete(num) res.push(num) } } return res };
No. In the worst case, there could be no duplicates and you add the whole array. Actually, this is basically never constant space. Basically the only time it would be is if all the numbers in the input are duplicates and the duplicates are always right next to each other.
🤦🏿♂️ I thought sorting was log n not nlogn. I hate not being able to come up with solutions like these. I almost always have to see the solution. Was super excited to have come up with this. Back to the drawing board I guess
@@MyMojoSoDopeNights yeah, O(logn) is Binary Search. normal sorting algo internally is quick sort which is what makes it O(nlogn). Anyways this is the process you need to go through. If you give up during this journey you will not be a master. To be a master, or a chief grandmaster, you need to accept your defeat and show up everyday. And then there's some light at the end of the tunnel. Good luck! And happy coding bro. 🤓
In leetcode problems, pretty much. If the answer is an array of 5 elements, there’s nothing you can do to make it an array of 4 elements. By doing so you’d have the wrong answer. What you might be able to do is limit the extra space needed to achieve the answer. In this case he went for O(n) to O(1). But since the right answer is independent of the algorithm, it doesn’t help to include it when comparing algorithms. In the real world though, you would include it.
if we solve this using a hashmap the space complexity should still be O(1) because at the worst case we will be adding 26 characters to the hashmap. Right???
![🎤 จับฉลากร้องเพลง x P’ #XXSIVK [EP.1] (2/2) เพื่อนจับได้คำไหน..ต้องร้องคำนั้น เริ่ม! 💓🎶 #MXFRUIT](http://i.ytimg.com/vi/1bJvMJXmeS4/mqdefault.jpg)
trick: whenever the question says numbers something about whole numbers until n, see if marking the index by making its value negative helps
thanks for the tip
Solved it in O(n) and constant space !! A beautiful problem . The O(n) approach is really elegant and smart.
Quite a smart way to map the value itself to the respective index position (value - 1) in the nums array since the the array will always contain the numbers ranging from 1 to n.
I couldn't figure it out without using a hash set. Thanks for the solution.
After reading cyclic sort technique, this solution make me feel more clear!
Should we assume we can use the input array as extra memory when we face this kind of problem in an interview? I thought this might be a bad practice in real world scenarios.
It's prob worth confirming with your interviewer before you start coding it. Fwiw it would be easy to revert the changes we made to the array if the interviewer prompted us to.
Your coding interview is not supposed to reflect how you code in a normal environment, it’s meant to show your mentality. This problem in particular presents your ability to be resourceful
i think this is a mistake on their behalf but arent you making an extra array res that in the worst case gonna be of length O(n/2) which simplifies to O(n) ?, also here's a problem that is basically the same as this one for people who wanna solve it (yesterday's problem) : 287. Find the Duplicate Number
if you use a different property, you can do it in true O(1) space complexity by returning the input array after modification
this involves adding n+1 to elements when visited and using %(n+1) to check further indexes
u can then test for all values greater than 2(n+1) and change them to their index values (note the 1-indexing) and remove from list in O(1) for at worst n items, as relative order doesnt matter and thus removal can be done by swapping to end of array
i think this approach adheres to the spirit of the question much better
:)
This is epic. I can never come up with this idea on my own. Despite I use collections.Counter and list comprehension to reach to beat-85% runtime speed, your idea is still brilliant.
Index sort works as well!!
already solve it, with my own intuition of cycle sort but I feel its not very efficient although it was O(n) time, now I'm here to get more efficient solution
There’s actually a constant space and constant *time* solution. Basically you choose a random index and add that to the result array, then return immediately. The downside is that it has an accuracy complexity of P(1/N^2) avg case and P(0) worst case, however when it works it’s da best!
Which dummy gave this soln a thumbs up ??
I’d solve this with the hare and tortoise algorithm, mutating the base array to keep a Constant space is hacky for me (and would not to be possible in functional langs), pretty straightforward solution tho
Cyclic sort is another solution
Alternative solution: you walk through the array,
if a[i] - 1 = i, continue.
If a[a[i] - 1] !=a[i], you swap them. Keep swapping until you either unravel the whole cycle, or you find a duplicate. If you find a duplicate, you can mark it and continue.
Very similar, performance characteristics I believe.
i don't think that would work in O(n) time. Take for example the array 3 3 4 4
@@CrabGuyy no it is o(n).analyze it on your own
Thanks for the video. Do you sometimes skip daily questions even if you didn't solve them? Because I don't remember exactly which dates (february or march) but I looked for the daily questions but I couldn't find them.
generally speaking if ain't done in-place it's pretty much O(n) extra memory regardless. And can't think of solution less then O(nlogn) time which could swap out dupes somehow.
Nice unexpected solution.
Hi nice solution does this logic work when we have a test case like this n =4 and nums = [3,3,3,3] this would return res =[3,3] and we would have duplicates in the result array so we may need to add a condition to check if that number is already present in the result list? Thanks in advance @neetcodeio
Question says each element in input list occurs atmost twice, so your input is not possible
This is so clever
Simple and wonderful as usual.
Find the Duplicate Number Is very similar. It how I solved this question really fast
Brilliant❤❤❤❤
ingenious as always
Thank you!
Well when I saw the thumbnail of the video, I went straight to the leetcode and tried solving the problem myself . So thing that was confusing me was that we have to use constant extra space otherwise we could use a HashSet and store all the elements and then check if any element is present twice we push that to the result array or we could iterate through the array twice but that would be O(n2).
So then I thought of the Dictionary(Key-Value) . So we can simply generate a frequency map using a for/foreach loop and keep track of the elements frequencies using a dictionary and when the frequency of an element equal 2 we push that to the result. So sine dictionary is not dependent on input array it's constance space and we are iterating through the array once so it's O(n).
I'm getting better though xD.
That's not constant space. This is just the hash set solution with minor modifications. The dictionary is totally dependent on the input array since you add all values in the input array to the dictionary.
@@1vader You're correct that's O(n) space complexity since we're storing the frequencies of all elements of the input array. Shit
This assumes mutability of the input data. You are still using O(n) space since you are "stealing" one bit from each array position to use as a flag and you need n of them.
Its a clever solution to a problem that has a very badly specified question.
hi, for a input {8, 8, 7} it will give arrayoutofBound right?
you can't have that input. for an array of length 3 only possible values are 1, 2, 3. read problem again
can you do "126. Word Ladder II"? You have done 127, but this one is more specific and it can easily go to TLE. I cannot find a clear video solution for 127.
I feel like you’ve done a video before where you use this trick of making values negative, can’t remember what the problem was though
Hey bro , i have a question to you , in today's market 40% jobs are on tool base d technologies like devops enginner , RPA developer , etccc . So Top product based companies work on these tools and sell these ools like microsodt developed power automate for RPA engineers . Sales force created muel soft for API developement . So it is good to go for working on these tool based techh orgo for DSA and work on creation of these technn. I request you to make a video these because , i see you have digging knowledge in Technology . Its a request .
I 'am confused the problem says 'only constant extra space.' but we are using res as an array and appending to it
you can ignore the space for creating res array, problems mean use only constant computation space (intermediate storage)
Similar logic explained for 41.First Missing Positive
Looks like this method could be applied to yesterday's
287. Find the duplicate number also
True but yesterday's question specifically asked not to change the input array itself. So Floyd's Tortoise and Hare algorithm might be the only optimal solution based on yesterday's constraints
@@oneepicsaxguy6067 oh! my bad
Would it also be O(1) if we remove duplicate from set after finding it?
function findDuplicates(nums: number[]): number[] {
const res = []
const set = new Set()
for (const num of nums) {
if (!set.has(num)) {
set.add(num)
} else {
set.delete(num)
res.push(num)
}
}
return res
};
No. In the worst case, there could be no duplicates and you add the whole array. Actually, this is basically never constant space. Basically the only time it would be is if all the numbers in the input are duplicates and the duplicates are always right next to each other.
ur the goat
when ever you see 1 to n or 0 to n use cyclic sort.
in cpp
class Solution {
public:
vector findDuplicates(vector& nums)
{
vector ans;
for(int &it:nums)
{
int index=abs(it)-1;
if(nums[index]
Beast
Just sorted it and checked if nums[r] == nums[r-1] seemed to pass 🤷🏽♂️
That is O(nlogn) time complexity
lol thought about it in 1 minute coded it too. but thats not what matters.all that matters is O(n) TC.
🤦🏿♂️ I thought sorting was log n not nlogn. I hate not being able to come up with solutions like these. I almost always have to see the solution. Was super excited to have come up with this. Back to the drawing board I guess
@@MyMojoSoDopeNights yeah, O(logn) is Binary Search. normal sorting algo internally is quick sort which is what makes it O(nlogn). Anyways this is the process you need to go through. If you give up during this journey you will not be a master. To be a master, or a chief grandmaster, you need to accept your defeat and show up everyday. And then there's some light at the end of the tunnel. Good luck! And happy coding bro. 🤓
287. Find the Duplicate Number
i have a doubt
if u are appending to res doesnt it make O(n) space?
the problem statement states that return the array which is the result right
@@kailashnaidu8268 hm
Usually the answer (in this case the res array) isn’t counted towards extra space
@@SegmentationFaultCoreDumped for every problem?
In leetcode problems, pretty much. If the answer is an array of 5 elements, there’s nothing you can do to make it an array of 4 elements. By doing so you’d have the wrong answer. What you might be able to do is limit the extra space needed to achieve the answer. In this case he went for O(n) to O(1). But since the right answer is independent of the algorithm, it doesn’t help to include it when comparing algorithms. In the real world though, you would include it.
Why would you make it positive if it was seen once? Seems they lacked a testcase with more than 2 occurrences
😱
if we solve this using a hashmap the space complexity should still be O(1) because at the worst case we will be adding 26 characters to the hashmap.
Right???
Let me know if you get the answer and i still don't understand what is constant space if we are still using additional data structure
Where are you getting 26 characters from? You are adding all numbers in the array which is O(n).
leetcode 448: Find All Numbers Disappeared in an Array
I solved this without watching the video, NC pro