Generally we say "non-decreasing order" if the elements in the array are not strictly ascending like: [1,2,3,4,5], "non-decreasing order" means array can have elements like "[1,1,2,2,3]", not strictly ascending. Similar is the case for "non-increasing order".
For anyone who is seeing this comment, don't feel ashamed of watching the solution for an easy level leetcode, keep the grit and keep grinding. You'll eventually succeed!
At the end of the day, the task is to understand / be able to do what you previously did not understand / were not able to do. Whether you do it yourself or it's a learning experience for you, progress is nevertheless being made. For me, I'm trying to use my limited time efficiently so I'd rather look at the solution and internalize the logic and syntax then spend however much longer trying to solve it for myself (and possibly end up having to spend time learning the solution from scratch anyway).
0:28, because In mathematics, a sequence is said to be in non-decreasing order if each term is greater than or equal to the one before it. In other words, the sequence does not decrease at any point.
To me, i was confused on how to prevent redundancy. I thought "ok. Let's use 2 pointers and have one start at 0 while the other starts at the next value. Keep the left pointer at one element while the right pointer increments upon every iteration. If both elements are same, then the loop keeps incrementing. If not, swap the values and then increment the left pointer.". I will leave it up to you to see the flaw in this logic.
I don't have lc account, but code from 10:15 doesn't replace duplicates with null/none/blank space/etc... this does: def removeDuplicates(nums): l = 1 for r in range(1, len(nums)): if nums[r] != nums[r-1]: nums[l] = nums[r] l += 1 for i in range(l, len(nums)): nums[i] = None return nums nums = [1, 2, 2, 3, 4, 4, 4, 5, 5] removeDuplicates(nums) print(nums) # output: [1, 2, 3, 4, 5, None, None, None, None]
This problem is written like shit. This comment helped solve it without watching the solution: "They don't really want you to remove the duplicates. They want you to sort the uniques at the front, then return the length of the sorted part. Then, behind the scenes, they slice the array at the length you give them and the result of that is what they check. Just FYI, this sh_t drove me crazy..."
Yep this is the only thing that explains why we are not exactly "removing" duplicates from the array, a comment on LeetCode lol. We return the number they use to splice the array, it was excruciating trying to figure out what I was supposed to do with the rest of the freaking array!
10:04 u said what if we have an empty array , but according to the constraints , the minimum length of input will be 1 so that is why leetcode accepts it: constraint: 1
Im ngl, this actually made sense. Was looking at the solution like why do all of this. I hate that none of this is visual on leetcode but this really helped
Such a clear explanation and easy to understand solution, thank you man. This was way better explained and coded than the example on Grokking the Coding Interview
i used a map to track unique values and if i found the number before i spliced it out of the nums array and decremented the loop (to recheck for an indexOf from that position). i didnt use pointers but i had to use more memory.
This is my solution, but yours is better: def removeDuplicates(self, nums: List[int]) -> int: l = 0 r = 0 # or 1? while r < len(nums): while r+1 < len(nums) and nums[r] == nums[r+1]: r += 1 nums[l] = nums[r] r += 1 l += 1 return l
Thank you! I was a bit confused because I thought you had to null all the other values in the updated array, because the question had _ representing those indices.
Java solution: public static int removeDuplicates(int[] arr) { int left = 1; for (int right = 1; right < arr.length; right++) { if (arr[right] != arr[right - 1]) { arr[left] = arr[right]; left++; } } return left; }
dislikes for this problem on the leetcode are from everyone who tried to create a new array from num. Not "in-place". It did that too, misread this part of requirements 😪
Well, I came up with similar approach, using count and last seen element. I actually forgot that this is a classic two pointer problem 😅 which I already had worked on before.
Does anyone have problem running this code with zero or negative value's array on leet code simulation? Whenever i run array that has zero or negative value, the loop left out the very last value.
My test cases were accepted but my final submission didn’t get accepted because it exceeded the time limit. That was just a clear reflection of how I code, inefficient but getting the job done. My house is burning but hey, at least we got heat.
I actually spend so much time solving it.. that too by shifting the elements but it could have done a much simpler way. I really don't know if I will ever get good enough to reach the point where the best solution just clicks after some thinking .it's so frustrating
this solution is uncharacteristically confusing for Neetcode. My recommended solution: prevNum = -101 i = 0 while i < len(nums): if nums[i] == prevNum: # repeat nums.pop(i) i -= 1 #keep the loop the same else: #not repeat prevNum = nums[i] i +=1 return len(nums)
So, I did the same thing first off when i read the question. But the problem with this is - popping an element from the index (i) takes O(n) complexity. so your solution is having the complexity of O(n^2). On the other hand, the solution in the video shows the approach of 2 pointers and achieves the answer in a single pass. You can try submitting your answer but will see a time inefficiency in the submission but your approach is absolutely correct.
def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ x = 0 while x < len(nums): val = nums[x] if nums[x+1:].count(val) >= 1: # nums.remove(val) nums[x+1:] = list(filter(lambda a: a != val, nums[x+1:])) else: x += 1 return len(nums) How is this approach?
Why is this code not working for the solution? class Solution: def removeDuplicates(self, nums): uniqueset = set() for n in nums: uniqueset.add(n) return len(uniqueset) I've tried this outside of LeetCode's checkers and it returns an integer of the expected length. Doing print(uniqueset) returns a set of the expected values, but Leetcode's checker says it returns a completely different list of values. I'm very confused as to what has gone wrong, but I am new to Python3.
Having watched the start of the video, you say that we can't initialise another array (and presumably a set as I've used) but this is not the state of the problem on the website today 1yr after this video was posted. It simply says to return k. Utterly stupid problem, just gonna skip this one.
@@Sabre5106 u should modify nums inplace according to the problem its more important than returning the length of unique elements. When u submit the code they check both nums and the value u r returning but u are not modifying the nums list
Wait until they learn about the word monotonic! Unfortunate as it is, non-decreasing, monotonic, whatever you want to use is actually the most mathematically precise way to express the problem constraints. Try and not resist these unfamiliar words but embrace the confusion as a learning opportunity!
public int removeDuplicates(int[] nums) { int k = 1; // k is the left pointer for (int i = 1; i < nums.length; i++) { // ? i is the right pointer if (nums[i] != nums[i - 1]) nums[k++] = nums[i]; } return k; }
i did not understand when i try to use hash set and return the count of hash leetcode return me a error can we solve this problem with hash set? if its not why?
Sorry if it’s too late but it’s because the problem requires you to not allocate extra space. There’s probably an edge case where each element is unique, like all evens [2,4,6,8] Worst case scenario, your hash grew to the space time to O(n). Problem requires an O(1) space time solution.
Hey NeetCode Can't we simply do like: k = set(nums) return list(k) The set function automatically removes duplicates. Still it's showing error. Can you please explain why set function isn't working
@@lucifers6105 actually I later realised that set function doesn't perform the operation inplace. Instead it creates an temporary array for the same. 😁
@@dipanjanjayswal554 I think you are right but still, I managed to find a way to make work with a set implementation. new_nums = set(nums) new_nums = list(new_nums) new_nums.sort() for i in range(len(nums)): try: nums[i] = new_nums[i] except: nums.pop() return len(nums)
The algorithm still works for your case . [1,2,3,4,4] L=1, R=1 First loop, if condition is true, so we place nums[R] at index L, so "replace" 2 with 2. Increment both pointers. Same thing happens for 3 and 4. We finally get to the duplicate 4, we'd leave the L pointer behind and only increment R pointer.
The reason why the problem has so many dislikes is because the description for the task of this problem was horribly explained and seems to be intentionally unclear. It's verbose for literally no reason and the examples don't actually show what you're literally supposed to return. They show a number and a modified array, when you're just supposed to return the number, even though the expected result in the test cases show a modified array but don't show the number for k. You literally don't have to modify the array at all, even though the problem tells you to, and the solution would still get accepted as long as you return the right number.
What is the problem? Everything works fine in my paycharm, but not on the litcode class Solution: def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ tmp = [] for i in nums: if i not in tmp: tmp.append(i) nums = tmp return len(tmp) ------------------------------------------------------------------ Input nums = [0,0,1,1,1,2,2,3,3,4] Output [0,0,1,1,1] Expected [0,1,2,3,4]
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
no more free
Generally we say "non-decreasing order" if the elements in the array are not strictly ascending like: [1,2,3,4,5], "non-decreasing order" means array can have elements like "[1,1,2,2,3]", not strictly ascending. Similar is the case for "non-increasing order".
Makes sense now!
💯
I'm glad I came here and read the comments.
"Return the number of unique values in the array" is SO much better than saying "Return k", thank you!
Been spending the last 3hours trying to solve this problem.
Your explanations are very clear dude.
Thanks
same here
yeah this problems confusing, maybe correlates with the many dislikes for this problem
I still not able to understand this
Was really confused about this problem until watching this video. The solution is so elegant.
For anyone who is seeing this comment, don't feel ashamed of watching the solution for an easy level leetcode, keep the grit and keep grinding. You'll eventually succeed!
At the end of the day, the task is to understand / be able to do what you previously did not understand / were not able to do. Whether you do it yourself or it's a learning experience for you, progress is nevertheless being made. For me, I'm trying to use my limited time efficiently so I'd rather look at the solution and internalize the logic and syntax then spend however much longer trying to solve it for myself (and possibly end up having to spend time learning the solution from scratch anyway).
Leetcode has the constraint : 1
0:28, because In mathematics, a sequence is said to be in non-decreasing order if each term is greater than or equal to the one before it. In other words, the sequence does not decrease at any point.
2:40 That "say no more!" moment, where i literally stop watching and solve this problem. Understanding is king. Thanks a lot man!
To me, i was confused on how to prevent redundancy. I thought "ok. Let's use 2 pointers and have one start at 0 while the other starts at the next value. Keep the left pointer at one element while the right pointer increments upon every iteration. If both elements are same, then the loop keeps incrementing. If not, swap the values and then increment the left pointer.". I will leave it up to you to see the flaw in this logic.
Solved it first using a while loop, but using two pointers feels definitely much more easy to understand and explain.
Awesome videos dude, these have been a super helpful resource as I study for interviews
Non-decreasing means all numbers can be equal as well in the array.
I don't have lc account, but code from 10:15 doesn't replace duplicates with null/none/blank space/etc...
this does:
def removeDuplicates(nums):
l = 1
for r in range(1, len(nums)):
if nums[r] != nums[r-1]:
nums[l] = nums[r]
l += 1
for i in range(l, len(nums)):
nums[i] = None
return nums
nums = [1, 2, 2, 3, 4, 4, 4, 5, 5]
removeDuplicates(nums)
print(nums)
# output: [1, 2, 3, 4, 5, None, None, None, None]
Really like your explanations. I'm using JavaScript, but you make it so easy to undestand the problem and the solution for it.
The array cant be empty cuz the first constraint in the question is (1
w
i am so appreciative for this video cause my mind is not developed enough to learn on my own and finally i understood it thank u brother
This problem is written like shit. This comment helped solve it without watching the solution:
"They don't really want you to remove the duplicates. They want you to sort the uniques at the front, then return the length of the sorted part. Then, behind the scenes, they slice the array at the length you give them and the result of that is what they check.
Just FYI, this sh_t drove me crazy..."
Yep this is the only thing that explains why we are not exactly "removing" duplicates from the array, a comment on LeetCode lol. We return the number they use to splice the array, it was excruciating trying to figure out what I was supposed to do with the rest of the freaking array!
10:04 u said what if we have an empty array , but according to the constraints , the minimum length of input will be 1 so that is why leetcode accepts it:
constraint: 1
Such a clean and brilliant solution.
Oh my God... What an easy solution... And i was thinking all the complex way I can
I really feel you..
Im ngl, this actually made sense. Was looking at the solution like why do all of this. I hate that none of this is visual on leetcode but this really helped
Such a clear explanation and easy to understand solution, thank you man.
This was way better explained and coded than the example on Grokking the Coding Interview
did this on my own after checking your other vids, thanks to you Neetcode!
i used a map to track unique values and if i found the number before i spliced it out of the nums array and decremented the loop (to recheck for an indexOf from that position). i didnt use pointers but i had to use more memory.
Thanks!
Thank you so much Andrey!!!
You just made it so easy!
Thanks
Hey Srikanth - thank you so much, I really appreciate it!! 😊
Thank you, your approach was quite good enough. I just want to know how to think to come upon such a way to solve a problem?
Having a third pointer specifically for maintaing the unique value is much easier and more understandable thhan managing with two pointers
I struggled for hours!! Thanks
This is my solution, but yours is better:
def removeDuplicates(self, nums: List[int]) -> int:
l = 0
r = 0 # or 1?
while r < len(nums):
while r+1 < len(nums) and nums[r] == nums[r+1]:
r += 1
nums[l] = nums[r]
r += 1
l += 1
return l
Thank you! I was a bit confused because I thought you had to null all the other values in the updated array, because the question had _ representing those indices.
Java solution:
public static int removeDuplicates(int[] arr) {
int left = 1;
for (int right = 1; right < arr.length; right++) {
if (arr[right] != arr[right - 1]) {
arr[left] = arr[right];
left++;
}
}
return left;
}
10:00 1
You are awesome. Thank you for all the videos you made. They're really helpful for beginners.
dislikes for this problem on the leetcode are from everyone who tried to create a new array from num. Not "in-place". It did that too, misread this part of requirements 😪
Well, I came up with similar approach, using count and last seen element. I actually forgot that this is a classic two pointer problem 😅 which I already had worked on before.
This is genius! Best video on UA-cam, thanks bro!
Man, you're a gem!!
I think a rules-lawyer used non-decreasing because an array 0,0,0,0,0 does not increase/ascend
wow i just solved it and it felt so good
Does anyone have problem running this code with zero or negative value's array on leet code simulation? Whenever i run array that has zero or negative value, the loop left out the very last value.
What is wrong when I store these values in a and then print the size of the set?
You're using O(k) extra space
thanks for good work...crystal clear explanation..
when i run this it says it works but when i submit it says wrong answer because the output isnt in ascending order.
More optimised approach -
int removeDuplicates(std::vector& nums){
int n=nums.size();
int index = 2;
if(n
Great work 👍👍👍
Thanks!
so well explained thankyou
My test cases were accepted but my final submission didn’t get accepted because it exceeded the time limit. That was just a clear reflection of how I code, inefficient but getting the job done. My house is burning but hey, at least we got heat.
LeetCode accepts this solution because there is a constraint for len(nums) to be => 1, so there always be at list 1 unique number in nums
This is so well explained
Thats beautiful and elegant
Unlike mine 😂 but it works too
No one can replace you❤
I actually spend so much time solving it.. that too by shifting the elements but it could have done a much simpler way. I really don't know if I will ever get good enough to reach the point where the best solution just clicks after some thinking .it's so frustrating
You will !
hi, what drawing app are you using? thanks
You are amazing. keep doing the good work
anyone could please send the program that i could execute on my ide with using the same logic
please sir help me out i need this logic only as a sokution in my ide
this solution is uncharacteristically confusing for Neetcode. My recommended solution:
prevNum = -101
i = 0
while i < len(nums):
if nums[i] == prevNum: # repeat
nums.pop(i)
i -= 1 #keep the loop the same
else: #not repeat
prevNum = nums[i]
i +=1
return len(nums)
So, I did the same thing first off when i read the question.
But the problem with this is - popping an element from the index (i) takes O(n) complexity. so your solution is having the complexity of O(n^2).
On the other hand, the solution in the video shows the approach of 2 pointers and achieves the answer in a single pass.
You can try submitting your answer but will see a time inefficiency in the submission but your approach is absolutely correct.
great explanation
In my opinion, how about we used sort function? Answer : unique_arr = list(set(arr))
you need to have 0(1) space answer.
I came up with a crafty solution xD, but it's in O(n^2) !
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
x = 0
while x < len(nums):
val = nums[x]
if nums[x+1:].count(val) >= 1:
# nums.remove(val)
nums[x+1:] = list(filter(lambda a: a != val, nums[x+1:]))
else:
x += 1
return len(nums)
How is this approach?
if array like [0 1 2 2 3] and we are starting from index 1 then r # r+1 so we lose the value 1 cuz 2#1, can someone explain me pls
Why is this code not working for the solution?
class Solution:
def removeDuplicates(self, nums):
uniqueset = set()
for n in nums:
uniqueset.add(n)
return len(uniqueset)
I've tried this outside of LeetCode's checkers and it returns an integer of the expected length. Doing print(uniqueset) returns a set of the expected values, but Leetcode's checker says it returns a completely different list of values. I'm very confused as to what has gone wrong, but I am new to Python3.
Having watched the start of the video, you say that we can't initialise another array (and presumably a set as I've used) but this is not the state of the problem on the website today 1yr after this video was posted. It simply says to return k.
Utterly stupid problem, just gonna skip this one.
@@Sabre5106 u should modify nums inplace according to the problem its more important than returning the length of unique elements. When u submit the code they check both nums and the value u r returning but u are not modifying the nums list
Hey - love this content. Any ideas why this O(n) solution isn't just as fast as the other solutions, even though they are all pretty much O(n) time ?
It's not about time in this question. It's about extra space.
why using set gives wrong answer?
it prints the correct value in stdout but wrong in output
def removeDuplicates(self, nums: List[int]) -> int:
prev = None
j=0
for i in nums:
if i != prev:
nums[j] = i
j+=1
prev = i
return j
Hi Mr.Neet can you please cover the convex hull question erect the fence.
Wait until they learn about the word monotonic!
Unfortunate as it is, non-decreasing, monotonic, whatever you want to use is actually the most mathematically precise way to express the problem constraints. Try and not resist these unfamiliar words but embrace the confusion as a learning opportunity!
Great Explaination.
Thanks for your clear explaination, but what if the size of nums is 0 or 1?
We can't have duplicates if size is 0 or 1, so that wouldn't be a valid input I guess
public int removeDuplicates(int[] nums) {
int k = 1; // k is the left pointer
for (int i = 1; i < nums.length; i++) { // ? i is the right pointer
if (nums[i] != nums[i - 1])
nums[k++] = nums[i];
}
return k;
}
Isn't this too much for beginners, cuz they say it easy level
def removeDuplicates(self, nums: List[int]) -> int:
i=0
for j in range(1,len(nums)):
if nums[j] != nums[i]:
nums[i+1],nums[j] = nums[j], nums[i+1]
i += 1
return i + 1
Great explaination
not sure why i get an index out of bound getting the same output using golang
Does this channel not have ads?
easy with numbers what about strings ?
How do you call this code within the IDE. I'm always getting the message ....NameError: name 'List' is not defined
from typing import List
Why can't we just convert it to a set, and then convert it to a set and then return the length of the set?
because we should not use extra space in this question. This means we cannot take any other data structure.
i did not understand when i try to use hash set and return the count of hash leetcode return me a error can we solve this problem with hash set? if its not why?
Sorry if it’s too late but it’s because the problem requires you to not allocate extra space.
There’s probably an edge case where each element is unique, like all evens [2,4,6,8]
Worst case scenario, your hash grew to the space time to O(n). Problem requires an O(1) space time solution.
Hey NeetCode Can't we simply do like:
k = set(nums)
return list(k)
The set function automatically removes duplicates. Still it's showing error. Can you please explain why set function isn't working
I have the same exact problem, Like for real why doesn't it work with a set ??
@@lucifers6105 actually I later realised that set function doesn't perform the operation inplace. Instead it creates an temporary array for the same. 😁
@@dipanjanjayswal554 I think you are right but still, I managed to find a way to make work with a set implementation.
new_nums = set(nums)
new_nums = list(new_nums)
new_nums.sort()
for i in range(len(nums)):
try:
nums[i] = new_nums[i]
except:
nums.pop()
return len(nums)
@@morningstar3996 good approach dude.. out of the box thought 💭 👍🏻
Sorry but this code doesn't return the output array with non duplicate values?
Great man salute 😄nicely explained
About as efficient as it can get huh? But the LeetCode statistics aren't that reliable in terms of efficiency right?
I used a the len and a set but it would not accept the solution?
make sure your not creating a new instance of nums and your adding the sorted set to the original nums list
ex:
nums[:] = sorted(set(nums))
Can we say that it is some way a sliding window?
Problem seems to be very simple, but also seems to be written by an alien
This question really confuse me lol..the wording itself is a quiz
True! The solution is pretty simple, just the instructions are strange lol
What if we have [1,2,3,4,4] ? Two values are different, but if we go with this solution, we will end up overriding the unique values.
The algorithm still works for your case .
[1,2,3,4,4] L=1, R=1
First loop, if condition is true, so we place nums[R] at index L, so "replace" 2 with 2. Increment both pointers. Same thing happens for 3 and 4. We finally get to the duplicate 4, we'd leave the L pointer behind and only increment R pointer.
@@reisturm9296 Very good catch 👍
It will work
If input is [1,1,2] it will do [1,2,2] and l=2
So print [1,2]
But expected output is [1,2,_]
To do this you need to create new array
this is the best!
Thank you
when i put the same code you did I still didn't get the write answer
The reason why the problem has so many dislikes is because the description for the task of this problem was horribly explained and seems to be intentionally unclear. It's verbose for literally no reason and the examples don't actually show what you're literally supposed to return. They show a number and a modified array, when you're just supposed to return the number, even though the expected result in the test cases show a modified array but don't show the number for k.
You literally don't have to modify the array at all, even though the problem tells you to, and the solution would still get accepted as long as you return the right number.
i put the same codes but its saying theres an error
What is the problem?
Everything works fine in my paycharm, but not on the litcode
class Solution:
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tmp = []
for i in nums:
if i not in tmp:
tmp.append(i)
nums = tmp
return len(tmp)
------------------------------------------------------------------
Input
nums = [0,0,1,1,1,2,2,3,3,4]
Output
[0,0,1,1,1]
Expected
[0,1,2,3,4]
I hated this problem
thanks alot
Awesome as always🙌🏻
Thanks!