Remove Duplicates from Sorted Array - Leetcode 26 - Python
Ғылым және технология
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/remove-...
0:00 - Read the problem
2:12 - Drawing Explanation
8:24 - Coding Explanation
leetcode 26
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.
Пікірлер: 148
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
@iiju8212
Жыл бұрын
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".
@beyzayildirim0
2 жыл бұрын
Makes sense now!
@predatorgaming895
2 жыл бұрын
💯
@scpcomm1215
11 ай бұрын
I'm glad I came here and read the comments.
Been spending the last 3hours trying to solve this problem. Your explanations are very clear dude. Thanks
@ganeshmurmu2338
Жыл бұрын
same here
@erniewang399
Жыл бұрын
yeah this problems confusing, maybe correlates with the many dislikes for this problem
@kanishkaakarthigayan8376
11 күн бұрын
I still not able to understand this
Awesome videos dude, these have been a super helpful resource as I study for interviews
"Return the number of unique values in the array" is SO much better than saying "Return k", thank you!
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
Really like your explanations. I'm using JavaScript, but you make it so easy to undestand the problem and the solution for it.
Was really confused about this problem until watching this video. The solution is so elegant.
Leetcode has the constraint : 1
You are awesome. Thank you for all the videos you made. They're really helpful for beginners.
did this on my own after checking your other vids, thanks to you Neetcode!
The array is already sorted. Below is my 1 pointer approach class Solution(object): def removeDuplicates(self, nums): left = 0 while left if nums[left] == nums[left + 1]: del nums[left] else: left +=1 return len(nums)
@denysivanov3364
3 ай бұрын
popping element from the middle is 0(n) operation in worst case. You only pop from the end in 0(1) from array (or when you pop and make empty space in the middle, otherwise values need to be copied). Double ended queue has O(N) pop from head and tail.
@fiafps
3 ай бұрын
this is O(N^2), make sure youre aware on how costly each array operations is
Such a clean and brilliant solution.
Non-decreasing means all numbers can be equal as well in the array.
Solved it first using a while loop, but using two pointers feels definitely much more easy to understand and explain.
2:40 That "say no more!" moment, where i literally stop watching and solve this problem. Understanding is king. Thanks a lot man!
@crimsonghoul8983
3 ай бұрын
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.
You just made it so easy!
thanks for good work...crystal clear explanation..
You are amazing. keep doing the good work
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.
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.
when i run this it says it works but when i submit it says wrong answer because the output isnt in ascending order.
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?
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.
This is so well explained
Great explaination
hi, what drawing app are you using? thanks
Great Explaination.
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.
so well explained thankyou
The array cant be empty cuz the first constraint in the question is (1
@jaredthompkins2472
Жыл бұрын
w
Oh my God... What an easy solution... And i was thinking all the complex way I can
@T_tintin
Жыл бұрын
I really feel you..
Great work 👍👍👍
@NeetCode
2 жыл бұрын
Thanks!
Having a third pointer specifically for maintaing the unique value is much easier and more understandable thhan managing with two pointers
great explanation
this is the best!
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
not sure why i get an index out of bound getting the same output using golang
I think a rules-lawyer used non-decreasing because an array 0,0,0,0,0 does not increase/ascend
Hi Mr.Neet can you please cover the convex hull question erect the fence.
Thank you
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.
thanks alot
Thanks!
@NeetCode
2 жыл бұрын
Thank you so much Andrey!!!
What is wrong when I store these values in a and then print the size of the set?
@deluksic
3 ай бұрын
You're using O(k) extra space
thank you
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 ?
@venkatasriharsha4227
2 жыл бұрын
It's not about time in this question. It's about extra space.
More optimised approach - int removeDuplicates(std::vector& nums){ int n=nums.size(); int index = 2; if(n
Thats beautiful and elegant Unlike mine 😂 but it works too
This is genius! Best video on KZread, thanks bro!
No one can replace you❤
i put the same codes but its saying theres an error
can someone please tell me what argument is -> int is
anyone could please send the program that i could execute on my ide with using the same logic
@rohitkumarjha3406
Жыл бұрын
please sir help me out i need this logic only as a sokution in my ide
thanks
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.
How do you call this code within the IDE. I'm always getting the message ....NameError: name 'List' is not defined
@gunahawk6893
2 жыл бұрын
from typing import List
why using set gives wrong answer? it prints the correct value in stdout but wrong in output
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
I came up with a crafty solution xD, but it's in O(n^2) !
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!
@doc9448
3 ай бұрын
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).
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..."
@JohnBalzac
7 ай бұрын
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!
Great man salute 😄nicely explained
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?
@SuubUWU
4 ай бұрын
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.
Sorry but this code doesn't return the output array with non duplicate values?
when i put the same code you did I still didn't get the write answer
Thanks for your clear explaination, but what if the size of nums is 0 or 1?
@yonahbyarugaba
2 жыл бұрын
We can't have duplicates if size is 0 or 1, so that wouldn't be a valid input I guess
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
@Pratik-tk6ts
Жыл бұрын
You will !
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.
@Sabre5106
10 ай бұрын
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.
@goldberg6330
10 ай бұрын
@@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
I tried one thing class Solution(object): def removeDuplicates(self, nums): answer=[] answer.append(nums[0]) uniquenums=1 for i in range(len(nums)): if nums[i] not in answer: uniquenums=uniquenums+1 answer.append(nums[i]) return uniquenums I don't know why it's not coming at all. Despite it being logically correct. Can somebody help me with this. When I checked it in the IDE it is coming perfectly, but when it comes to Leetcode it returns 1 as the output. Please help
@alanjerryson883
2 ай бұрын
same
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
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]
Does this channel not have ads?
easy with numbers what about strings ?
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?
@eklavya_axioms
Жыл бұрын
because we should not use extra space in this question. This means we cannot take any other data structure.
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.
@reisturm9296
2 жыл бұрын
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.
@prafulparashar9849
2 жыл бұрын
@@reisturm9296 Very good catch 👍
@T_tintin
Жыл бұрын
It will work
In my opinion, how about we used sort function? Answer : unique_arr = list(set(arr))
@8DMafia
10 ай бұрын
you need to have 0(1) space answer.
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
About as efficient as it can get huh? But the LeetCode statistics aren't that reliable in terms of efficiency right?
Awesome as always🙌🏻
@NeetCode
2 жыл бұрын
Thanks!
Thanks
@NeetCode
2 жыл бұрын
Hey Srikanth - thank you so much, I really appreciate it!! 😊
i don't understand why we can't use the pop function
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
2 жыл бұрын
I have the same exact problem, Like for real why doesn't it work with a set ??
@dipanjanjayswal554
2 жыл бұрын
@@lucifers6105 actually I later realised that set function doesn't perform the operation inplace. Instead it creates an temporary array for the same. 😁
@morningstar3996
2 жыл бұрын
@@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)
@dipanjanjayswal554
2 жыл бұрын
@@morningstar3996 good approach dude.. out of the box thought 💭 👍🏻
def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ x = 0 while x 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?
You saved my life
This question really confuse me lol..the wording itself is a quiz
@Lambyyy
2 жыл бұрын
True! The solution is pretty simple, just the instructions are strange lol
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 😪
public int removeDuplicates(int[] nums) { int k = 1; // k is the left pointer for (int i = 1; i if (nums[i] != nums[i - 1]) nums[k++] = nums[i]; } return k; }
This is my solution, but yours is better: def removeDuplicates(self, nums: List[int]) -> int: l = 0 r = 0 # or 1? while r while r+1 r += 1 nums[l] = nums[r] r += 1 l += 1 return l
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
why can't we return nums array sir?
@sajramkisho9991
2 жыл бұрын
because the return type is given as int and not int []
this solution is uncharacteristically confusing for Neetcode. My recommended solution: prevNum = -101 i = 0 while i 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)
@prafulparashar9849
2 жыл бұрын
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.
Java solution: public static int removeDuplicates(int[] arr) { int left = 1; for (int right = 1; right if (arr[right] != arr[right - 1]) { arr[left] = arr[right]; left++; } } return left; }
It not delete just reassign value
I hated this problem
Kinda similar to String Compression right?
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]
the assign right to left is silly ,it is pointless is easy if we just element the duplicates and assign just a single digit needs to be explained better
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