It's bizarre how many in-place problems you can solve using these exact lines of code (and some variant of the quicksort partition). Even more bizarre are the number of array problems that you can optimize for space complexity by turning them into in-place problems. Thank you so much!! I'm watching your videos concurrently with the Leetcode Arrays explore card, and everything is just starting to click and I can't believe I was just going into interviews this whole time without understanding how systematic your approach should be during interviews. I just practiced a ton and hoped I'd get lucky with stuff I remembered - but now I can reliably solve entire categories of problems with confidence every single time I see them in practice.
Hi. Can we link up. I am a freshman practicing leetcode also. I am grasping the concepts bit by bit, practicing towards a potential interview, and I would love the opportunity to chat with you and gain insights about your development.
Thank you for the wonderful explanation. If you just use [for n in nums:] instead of [for i in range(len(nums):] it slightly improves the runtime as you avoid redundant array element access using indexes.
This is really smart, I didn't think about this at all because I didn't understand the question, I thought it wanted us to SWAP the val with non val, but in truth, it doesn't really matter if val stays in the array or not, just that there is no val infront of non val, and we return the correct number of non vals.
The little disadvantage I see on this that is giving it such low score is exactly what was mentioned, that this is gonna perform the swap every time regardless of if its needed or not
not true! Assume: nums = [1,2,3] i = 0 j = 0 nums[i] = nums[j] The element of the array in this case "1" is the same(Same memory address), the thing that is changing is th index "i", "j".
Is it bad that I came up with the solution in which, every time 'val' found in the array, you have to shift all the elements from current pointer to the last index of the array to left by one place and decrement the last_index by 1. It took me a lot of time to get through the edge cases and all. I couldn't think about the solution you provided.
3 года назад+12
I think biggest reason that this question has so many down votes is mutability of arrays since they are "fixed sized" data structure.
@@pinakadhara7650 In general, arrays are fixed sized. That means, you can't (or at least too expensive) expand or shrink them. You can change their values but their size will be the same. en.wikipedia.org/wiki/Array_(data_structure) In past, the description was like: "Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory." which a lot of users were complained about this explanation.
@ description is quite clear. It doesn't expect us to change the length of array. After changing elements, we'd return the *size* of the array without the `val` elements , not a new array
Год назад+2
@@gradientO Old description was quite unclear, looks like it is updated.
In this case I used replace() in my Python solution since replace() is an in-place method. Resulted in a 4-line solution. Memory complexity was O(1) and runtime was 0ms (100%)
I have learnt this from your other videos , Why didn't you use 2 pointers solution which is O( n - number_of_occurrence_of_val) instead of O(n) ? any thoughts ?
# Take an easy solution for this problem class Solution: def removeElement(self, nums: List[int], val: int) -> int: i = 0 l = len(nums) while i < l: if nums[i] == val: # Just pop the element if it's equal to val nums.pop(i) l -= 1 else: i += 1 return len(nums)
im pretty sure .pop() updates the length of nums so doing "I -= 1" after "nums.pop(i)" isn't necessary right? I might be mistaken but I actually did the exact same thing you did without that
I solved it using a while loop which would simply remove the element from the list if the number is equal to val, otherwise it would increment the index. then we will finally return the index.
class Solution: def removeElement(self, nums: List[int], val: int) -> int: k = 0 for i in range(len(nums)): if val in nums: nums.remove(val) k += 1 return k How about this, it worked tho
Why can’t you just splice the element out since the other non-k elements will just fall in place when you splice the array? I don’t think that removes the O(n)
//My solution going backwards through public int removeElement(int[] nums, int val) { int last = nums.length - 1; //go through and just swap the val we dont want to the end pointer for(int i = nums.length - 1; i >= 0; i--){ if(nums[i] == val){ nums[i] = nums[last]; nums[last] = -1; last--; } } return last+1; }
this doesn't completely solve the problem though. we've to bring all the k non-value elements in the beginning of the array. with nums = [3, 2, 2, 3] and val = 2, while this alogrithm does calculate k = 2 correctly, the nums array will be [3, 3, 2, 3] at the end of the operation which is incorrect.
my bad, please ignore this comment. the question just specifies that the first k elements need to non-val. what's left of the other elements doesn't really matter.
Pythonic Solution class Solution: def removeElement(self, nums: List[int], val: int) -> int: length=len(nums) if val not in nums: return length l,r=0,length-1 while l=r: return l nums[l],nums[r]=nums[r],nums[l] l+=1 return l
You can make it faster by swapping non-val numbers from the back of the array. Just use another pointer from the back of the array. Stop the swapping when your "front pointer" is greater than or equal to your "back pointer". Hope that helps
class Solution(object): def removeElement(self, nums, val): for v in nums[:]: if v==val: nums.remove(v) return len(nums) This is faster than 70% of answers
class Solution(object): def removeElement(self, nums, val): for i in range(0,len(nums)): if val in nums: nums.remove(val) print(nums) c1 = Solution() nums = [3,2,2,3] val = 2 c1.removeElement(nums,val)
"v in nums" is O(n), also "nums.remove()" is O(n) so in the worth case, let's say, nums is only composed of "val" (nums = [val, val, val...]), you solution's time complexity is O(n^2).
Hey bro i just started with leetcode and i can't solve any questions even the easy one. How do i approch a problem man. Can you please make a videos in it. I feel dumb.
@@PAUL-ky4dq Funny enough, the skills you're gonna end up using during the job have little or nothing to do with what they ask in the interviews. Sometimes it feels like you're just memorizing the answers to standardized questions
hey pal. I still feel that way too. I found a solution to this code that has 96% memory and 90% run time and it is very simple to understand. while a value is in the list, remove that value. then return the length of the list without the value. Makes sense? def removeElement(self, nums: List[int], val: int) -> int:
You shouldn’t look at it as “easy” even though it says easy. Easy means there is usually a super simple way to do it but if you do it in some elaborate way it’s not easy. Hope that makes sense. I actually do better with the medium problems bc I’m not great at noticing subtle patterns and mediums are more in line with my overthinking of every problem.
It's bizarre how many in-place problems you can solve using these exact lines of code (and some variant of the quicksort partition). Even more bizarre are the number of array problems that you can optimize for space complexity by turning them into in-place problems. Thank you so much!! I'm watching your videos concurrently with the Leetcode Arrays explore card, and everything is just starting to click and I can't believe I was just going into interviews this whole time without understanding how systematic your approach should be during interviews. I just practiced a ton and hoped I'd get lucky with stuff I remembered - but now I can reliably solve entire categories of problems with confidence every single time I see them in practice.
Hi. Can we link up. I am a freshman practicing leetcode also. I am grasping the concepts bit by bit, practicing towards a potential interview, and I would love the opportunity to chat with you and gain insights about your development.
Thank God, finally found someone who explains the concept so clearly
I didn't even knew what 'in-place' actually meant :/
(At least I know now)
Thanks!
Thank you for the wonderful explanation. If you just use [for n in nums:] instead of [for i in range(len(nums):] it slightly improves the runtime as you avoid redundant array element access using indexes.
This is really smart, I didn't think about this at all because I didn't understand the question, I thought it wanted us to SWAP the val with non val, but in truth, it doesn't really matter if val stays in the array or not, just that there is no val infront of non val, and we return the correct number of non vals.
i solved the first test case but wasn't able to solve the second
The little disadvantage I see on this that is giving it such low score is exactly what was mentioned, that this is gonna perform the swap every time regardless of if its needed or not
not true!
Assume:
nums = [1,2,3]
i = 0
j = 0
nums[i] = nums[j]
The element of the array in this case "1" is the same(Same memory address), the thing that is changing is th index "i", "j".
what is the time complexity of growth of this channel :)
exponential
O(1)
The explanation was excellent and I understand everything, the code wondering why it worked 🥺
he is overwriting the whole array not a single element that is why I Was wondering too
nums[k] = nums[i]
Seems similar to partition method of quick sort partition.
NeetCode you are the best I so much trust and believe you
Thanks for sharing all of this for free
Is it bad that I came up with the solution in which, every time 'val' found in the array, you have to shift all the elements from current pointer to the last index of the array to left by one place and decrement the last_index by 1. It took me a lot of time to get through the edge cases and all. I couldn't think about the solution you provided.
I think biggest reason that this question has so many down votes is mutability of arrays since they are "fixed sized" data structure.
Can you please explain? I didn't understand
@@pinakadhara7650 In general, arrays are fixed sized. That means, you can't (or at least too expensive) expand or shrink them. You can change their values but their size will be the same.
en.wikipedia.org/wiki/Array_(data_structure)
In past, the description was like: "Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory." which a lot of users were complained about this explanation.
@ description is quite clear. It doesn't expect us to change the length of array. After changing elements, we'd return the *size* of the array without the `val` elements , not a new array
@@gradientO Old description was quite unclear, looks like it is updated.
In this case I used replace() in my Python solution since replace() is an in-place method. Resulted in a 4-line solution. Memory complexity was O(1) and runtime was 0ms (100%)
i wrote it exactly like yours but my mistake was that i was returning ''nums'' and kept giving me errors
I have learnt this from your other videos , Why didn't you use 2 pointers solution which is O( n - number_of_occurrence_of_val) instead of O(n) ? any thoughts ?
# Take an easy solution for this problem
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
l = len(nums)
while i < l:
if nums[i] == val:
# Just pop the element if it's equal to val
nums.pop(i)
l -= 1
else:
i += 1
return len(nums)
im pretty sure .pop() updates the length of nums so doing "I -= 1" after "nums.pop(i)" isn't necessary right? I might be mistaken but I actually did the exact same thing you did without that
I solved it using a while loop which would simply remove the element from the list if the number is equal to val, otherwise it would increment the index. then we will finally return the index.
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k = 0
for i in range(len(nums)):
if val in nums:
nums.remove(val)
k += 1
return k
How about this, it worked tho
what is the time and space complexity. of this algorithm?
Why can’t you just splice the element out since the other non-k elements will just fall in place when you splice the array? I don’t think that removes the O(n)
Worst-case scenario of splice is O(n) because the remaining elements need to be shifted
//My solution going backwards through
public int removeElement(int[] nums, int val) {
int last = nums.length - 1;
//go through and just swap the val we dont want to the end pointer
for(int i = nums.length - 1; i >= 0; i--){
if(nums[i] == val){
nums[i] = nums[last];
nums[last] = -1;
last--;
}
}
return last+1;
}
Similar to Move Zeroes to end.
Yeah, exactly!
thanks for the explanation
this doesn't completely solve the problem though. we've to bring all the k non-value elements in the beginning of the array. with nums = [3, 2, 2, 3] and val = 2, while this alogrithm does calculate k = 2 correctly, the nums array will be [3, 3, 2, 3] at the end of the operation which is incorrect.
my bad, please ignore this comment. the question just specifies that the first k elements need to non-val. what's left of the other elements doesn't really matter.
hi
your video of Leetcode 2002 is now a wrong answer. always getting TLE now
Brother , I am here to learn. In my perception , I think there may a problem when we use [3,2,2,3] according your code.Waiting for your reply
after simulate i found 2,2,2,3 . and the value of k is 2(This part is right)
Pythonic Solution
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
length=len(nums)
if val not in nums: return length
l,r=0,length-1
while l=r: return l
nums[l],nums[r]=nums[r],nums[l]
l+=1
return l
You can make it faster by swapping non-val numbers from the back of the array. Just use another pointer from the back of the array. Stop the swapping when your "front pointer" is greater than or equal to your "back pointer". Hope that helps
The array isn’t sorted so the right pointer isn’t finding non vals any faster
The example 2 output should be [0,1,3,0,4]
you're a legend, man
nice explanation !!!
This is genius!
thx！
Read-Write pointer :)
This is NOT an Easy question lmao
Omg bro...I tried to do this, ended up having 24 lines of code and you do it in 8 lmao
practice makes perfect, keep going 👍🏻
class Solution(object):
def removeElement(self, nums, val):
for v in nums[:]:
if v==val:
nums.remove(v)
return len(nums)
This is faster than 70% of answers
how do you give list as input though
class Solution(object):
def removeElement(self, nums, val):
for i in range(0,len(nums)):
if val in nums:
nums.remove(val)
print(nums)
c1 = Solution()
nums = [3,2,2,3]
val = 2
c1.removeElement(nums,val)
This modifies the array so it wont work in a real interview even if leetcode accepts it
Bro forgot the point of doing leetcode 🗿🗿🗿🗿🗿
"v in nums" is O(n), also "nums.remove()" is O(n) so in the worth case, let's say, nums is only composed of "val" (nums = [val, val, val...]), you solution's time complexity is O(n^2).
Hey bro i just started with leetcode and i can't solve any questions even the easy one. How do i approch a problem man. Can you please make a videos in it. I feel dumb.
Same haha. Ironically I already made many huge web applications
@@PAUL-ky4dq Funny enough, the skills you're gonna end up using during the job have little or nothing to do with what they ask in the interviews. Sometimes it feels like you're just memorizing the answers to standardized questions
hey pal. I still feel that way too. I found a solution to this code that has 96% memory and 90% run time and it is very simple to understand. while a value is in the list, remove that value. then return the length of the list without the value. Makes sense?
def removeElement(self, nums: List[int], val: int) -> int:
while val in nums:
nums.remove(val)
return len(nums)
You shouldn’t look at it as “easy” even though it says easy. Easy means there is usually a super simple way to do it but if you do it in some elaborate way it’s not easy. Hope that makes sense. I actually do better with the medium problems bc I’m not great at noticing subtle patterns and mediums are more in line with my overthinking of every problem.
you can add another condition to make it even faster:
if (nums[i] !== val) {
if (k !== i) {
nums[k] = nums[i];
}
k++;
}
I don't understand how you did this
While (val in nums):
nums.remove(val)
len(nums)
Is this wrong?
..... you forgot k += 1. When I attempted the question, it told me to return k. :/
im an idiot
same
❤
Thanks!