I was confused in this line I thought He did not wrote the hole condition but then I realise if 0 is present at ith index it will return fasle and if not then it will reurn true. So we don't hav to write hole condition here. Interesting humm!
neetcode is the best.. I am thinking of doing the neetcode gauntlet!! Do every problem that neetcode has completed from his first upload!!! Then I will be ready for MANGA
great video! A followup question is how would you keep all the zeros at the beginning and keeping the non zeros in order? E.g. [1,0,3,0,12] The only way I've found is using your method but start iterating at the end of the array. Wondering if there is another way to solve it. Thanks
Thanks a ton for simplifying problem statement at beginning because i derived similar logic with input = {0,0,0,12,4} but when change input = {8, 2, 0, 1,...} from java algo tutorial course, i got confused thinking my logic doing swap when leading pos elements are not zero but your simplifying problem here is trick i learn to justify to interviewers my var name was zeroPos but later renamed to slowPointer but left & right seem more suited :)
Wouldnt this solution swap even the non zeroes? for e.g. if the array is 1,4,3,0,2,1. During the second iteration wouldnt the numbers get swapped? How does this code ensure that only zeroes get swapped?
integs = [0,1,0,3,12] integs.sort() for x in range(len(integs)-1,-1,-1): if integs[x] == 0: a = integs.pop(x) integs.append(a) In [47]: integs Out[47]: [1, 3, 12, 0, 0]
@@MrMinecraftGamer456 In [7]: integs = [0,1,0,3,12] In [10]: [integs.append(integs.pop(x)) for x in range(len(integs)-1,-1,-1) if integs[x] == 0] In [11]: integs Out[11]: [1, 3, 12, 0, 0]
#Easy Python Solution - Two Pointers Approach class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ l = 0 for r in range(1,len(nums)): if nums[l] == 0 and nums[r] != 0: nums[l],nums[r] = nums[r],nums[l] l += 1 elif nums[l] != 0: l += 1
Thank you for your work, It would be amazing if we can get more than 1 solution, I guess that we have to find the worse and the best solution in an interview. Is this the best one? Cheers!
when 0s are not present in the list, this method swaps all the elements with itself. However, the following doesn't var moveZeroes = function(nums) { let left = 0; let right = 1; while(right < nums.length){ if(nums[left]){ left++; } if(nums[right] && nums[left] === 0){ const temp = nums[right]; nums[right] = nums[left]; nums[left] = temp; left++; } right++; } return nums; };
My notes for this problem """ Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. """ """ Approach 1: Using 2 pointer TC O(n) & SC O(1) 1. Basically, It is 2 pointer quesion. It seems very easy but the way it works is quite interesting. 2. Left pointer is putting every none-zero element at the right place. Wheneve left pointer find zero elemnt it will stick with it. 3. Right pointer is helping left pointer to find and put non-zero element at right place. we can say that right pointer is showing way to left pointer where to go. 4. What happens if we start right pointer from the second element instead of first? - In this case it will give wrong output. Because right pointer swap every non-zero item to left pointing item. so it will chage the order of list. - Swapping also occurs when right and left pointer both start from 0th position but in this case the swapping of element happens at the same place. which does not changes the order. """ def moveZeroes(nums): l=0 for r in range(0,len(nums)): #4 if nums[r]: nums[l],nums[r]=nums[r],nums[l] l+=1 return nums print(moveZeroes([0,1,0,3,12]))
Hi , You are doing great job!!....Could you please help in the question -- Making a Large Island (Leetcode 827). Would Really appreciate that!! Thanks a lot for all these videos :)
Unfortunately, your solution doesn't go with this input: nums = [1,0,1] The below solution deals with the abovementioned cases as well: def move_zeros(arr): i, j = 0, 1 while j < len(arr): if arr[i] == 0 and arr[j] != 0: arr[i], arr[j] = arr[j], arr[i] i += 1 j += 1 elif arr[i] != 0: i += 1 j += 1 else: j += 1
Why the solution doesn't work for [1,0,1] coding is based on logic...if it doesn't work for some input then the logic is wrong....Logic is correct and it will work
Of course the solution will work. See below step by step: 1. L = 0, R = 0, nums[R=0] = 1. So nums[R=0] != 0, Swap nums[L=0] = 1and nums[R=0] = 1, and L += 1. Current Array [1, 0 ,1] 2. L = 1, R = 1, nums[R=1] = 0, So nums[R=1] == 0, No action. Current Array[1, 0 ,1] 3. L = 1, R = 2, nums[R=2] = 1, So nums[R=2] != 0, Swap nums[L=1] = 0 and nums[R=2] = 1 and L += 1. Current Array [1, 1, 0] R = 3 > 2 , loop ends. And final array is [1, 1, 0], which is the correct output
the solution works, the main logic is to partition non-zero elements to the left, if the first element is non-zero, it is already partitioned to the left, so you can ignore it by shifting both left and right by +1. Read the solution again, both left and right pointers start at index 0. left pointer only stays when they encounter at 0. afterwards, the right pointer will traverse to find a non-zero element
nums[l], nums[r] = nums[r], nums[l], Do you means it will de these two at the same time, so we do not need a temp variable to swap. But we can not separate it to two line in python, right?
I'm not sure that would count as in place because it would technically change the size of the array, ex in Java its a sized array where the size can't change
If you mean by poping (removing) you will end up with an O(n^2) because removing from the middle is O(n) for arrays ! btw it is correct but not efficient !
Block of code after If statememt will run only if the condition is True. The condition will be False if it has a value of 0, anything other than 0 is True.
No partition is performed. It is a pointer method in which left starts from start index and right, one greater than start index. if R is greater than L, swap is performed else R moves +1
my approach was around 69ms and it only beat 7 % of people. its better to learn an algorithm that works in o(n). Your code worked for 238ms because of o(n)^2 time complexity like mine
@@NeetCode I think now you have to for i = l in range(nums) // set the remaining elements to zero // at the index starting from i // num[i] = 0 But it happens 🤣🙃
I absolutely love your approach and explanation.... Please upload more Amazon interview questions..I have interview coming up....
did you get the offer
Thank you for taking the time to do this, much appreciated!
I was confused in this line I thought He did not wrote the hole condition but then I realise if 0 is present at ith index it will return fasle and if not then it will reurn true. So we don't hav to write hole condition here. Interesting humm!
Wish I found this channel before I got this question during my interview
Ugh. I had this so close doing the problem on my own but caught up on some edge cases. Explanation is helpful!
Same
me too unless i un-pause other youtuber video tutorial for java who said to use pointer for zero;s position
neetcode is the best.. I am thinking of doing the neetcode gauntlet!! Do every problem that neetcode has completed from his first upload!!! Then I will be ready for MANGA
If you are confused about where does this patterns fits, read about partition alorithm. Thanks Neetcode.
specifically, lomuto's partition algorithm
great video! A followup question is how would you keep all the zeros at the beginning and keeping the non zeros in order? E.g. [1,0,3,0,12] The only way I've found is using your method but start iterating at the end of the array. Wondering if there is another way to solve it. Thanks
def solution(nums: list)->list:
count = nums.count(0)
for i in range(count): nums.remove(0)
for i in range(count): nums.append(0)
return nums
#Leetcode test cases
nums = [0, 1, 0, 3, 12]
result = solution(nums)
expected_output = [1, 3, 12, 0, 0]
assert result == expected_output, f"Expected {expected_output}, got {result}"
nums = [0]
result = solution(nums)
expected_output = [0]
assert result == expected_output, f"Expected {expected_output}, got {result}"
Thanks a ton for simplifying problem statement at beginning because i derived similar logic with input = {0,0,0,12,4}
but when change input = {8, 2, 0, 1,...} from java algo tutorial course, i got confused thinking my logic doing swap when leading pos elements are not zero but your simplifying problem here is trick i learn to justify to interviewers
my var name was zeroPos but later renamed to slowPointer but left & right seem more suited :)
Hi neetcode, thanks for posting i love ur videos so much! I would appreciate if u can post video on Longest Increasing Path in a Matrix!!
I got you fam, I'll upload it tomorrow morning!
@@NeetCode i love you ❤️
When I attempted myself, I kept trying to push the zeros forward rather than push the non-zeros back. I missed this insight and couldn't solve it.
Nice insights of simple algorithm. Thanks!
Wouldnt this solution swap even the non zeroes? for e.g. if the array is 1,4,3,0,2,1. During the second iteration wouldnt the numbers get swapped? How does this code ensure that only zeroes get swapped?
integs = [0,1,0,3,12]
integs.sort()
for x in range(len(integs)-1,-1,-1):
if integs[x] == 0:
a = integs.pop(x)
integs.append(a)
In [47]: integs
Out[47]: [1, 3, 12, 0, 0]
sort doesn’t work. You need to maintain order of non-zeros, which doesn’t necessarily mean sorted ordsr
@@MrMinecraftGamer456 the for loop will still work here without the sort
@@MrMinecraftGamer456
In [7]: integs = [0,1,0,3,12]
In [10]: [integs.append(integs.pop(x)) for x in range(len(integs)-1,-1,-1) if integs[x] == 0]
In [11]: integs
Out[11]: [1, 3, 12, 0, 0]
@@ChaseHatch bro shut up
Too many functions, you should know how to do it with basic data and structures.
your efforts are appreciated !!!!
#Easy Python Solution - Two Pointers Approach
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(1,len(nums)):
if nums[l] == 0 and nums[r] != 0:
nums[l],nums[r] = nums[r],nums[l]
l += 1
elif nums[l] != 0:
l += 1
Thank you for your work, It would be amazing if we can get more than 1 solution, I guess that we have to find the worse and the best solution in an interview. Is this the best one? Cheers!
Thank you for your work neet :D
This is such an awesome video
You are assuming the first element must be a zero. You need to initialize l and r by iterating until the first zero is encountered.
I coudln't solve this myself, so thanks a bunch!
Thanks a lot for this clear explanation
Greet explanation, thanks alot!
when 0s are not present in the list, this method swaps all the elements with itself. However, the following doesn't
var moveZeroes = function(nums) {
let left = 0;
let right = 1;
while(right < nums.length){
if(nums[left]){
left++;
}
if(nums[right] && nums[left] === 0){
const temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
left++;
}
right++;
}
return nums;
};
My notes for this problem
"""
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
"""
"""
Approach 1: Using 2 pointer
TC O(n) & SC O(1)
1. Basically, It is 2 pointer quesion. It seems very easy but the way it works is quite interesting.
2. Left pointer is putting every none-zero element at the right place. Wheneve left pointer find zero elemnt it will stick with it.
3. Right pointer is helping left pointer to find and put non-zero element at right place. we can say that right pointer is
showing way to left pointer where to go.
4. What happens if we start right pointer from the second element instead of first?
- In this case it will give wrong output. Because right pointer swap every non-zero item to left pointing item.
so it will chage the order of list.
- Swapping also occurs when right and left pointer both start from 0th position but in this case the swapping of element
happens at the same place. which does not changes the order.
"""
def moveZeroes(nums):
l=0
for r in range(0,len(nums)): #4
if nums[r]:
nums[l],nums[r]=nums[r],nums[l]
l+=1
return nums
print(moveZeroes([0,1,0,3,12]))
or just do : def moveZeroes(self, nums):
for i in range(len(nums)):
if nums[i] == 0:
nums.pop(i)
nums.append(0)
Hi , You are doing great job!!....Could you please help in the question -- Making a Large Island (Leetcode 827).
Would Really appreciate that!!
Thanks a lot for all these videos :)
You're Amazing!
Man, you are just great
Unfortunately, your solution doesn't go with this input: nums = [1,0,1]
The below solution deals with the abovementioned cases as well:
def move_zeros(arr):
i, j = 0, 1
while j < len(arr):
if arr[i] == 0 and arr[j] != 0:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j += 1
elif arr[i] != 0:
i += 1
j += 1
else:
j += 1
I would also move j+=1 outside the if/else and just write it once.
@@cherylto5898 yeahh) it would be better
Why the solution doesn't work for [1,0,1] coding is based on logic...if it doesn't work for some input then the logic is wrong....Logic is correct and it will work
Of course the solution will work. See below step by step:
1. L = 0, R = 0, nums[R=0] = 1. So nums[R=0] != 0, Swap nums[L=0] = 1and nums[R=0] = 1, and L += 1. Current Array [1, 0 ,1]
2. L = 1, R = 1, nums[R=1] = 0, So nums[R=1] == 0, No action. Current Array[1, 0 ,1]
3. L = 1, R = 2, nums[R=2] = 1, So nums[R=2] != 0, Swap nums[L=1] = 0 and nums[R=2] = 1 and L += 1. Current Array [1, 1, 0]
R = 3 > 2 , loop ends. And final array is [1, 1, 0], which is the correct output
the solution works, the main logic is to partition non-zero elements to the left, if the first element is non-zero, it is already partitioned to the left, so you can ignore it by shifting both left and right by +1.
Read the solution again, both left and right pointers start at index 0.
left pointer only stays when they encounter at 0.
afterwards, the right pointer will traverse to find a non-zero element
Really good explanation!
it frustrates me how simple the solution was
thank you!
nums[l], nums[r] = nums[r], nums[l], Do you means it will de these two at the same time, so we do not need a temp variable to swap. But we can not separate it to two line in python, right?
Either you can do this way swapping or the temp one, it depends on you
how about the following solution, is it as efficient?
for i in range(len(nums)):
if nums[i] == 0:
nums.remove(nums[i])
nums.append(0)
Very clean, but I think removing from the middle of an array is O(n) time complexity. So this would be O(n^2)
Won't it through an error as list size changed while iteration...
Doesn't work for [0,0,1]
Try this:
i = 0
while i < len(nums):
if nums[i] == 0:
nums.remove(nums[i])
nums.append('0')
else:
i+=1
@@anshbhatia1 what do you mean it won't work for [0,0,1]? It will work
thanks : )
Why are you returning? It's clearly mentioned not to return anything
LeetCode: Do not return anything, modify nums in-place instead
NeetCode: return nums
If you pop the 0 and append a 0 at the end of the list wont work?
I'm not sure that would count as in place because it would technically change the size of the array, ex in Java its a sized array where the size can't change
If you mean by poping (removing) you will end up with an O(n^2) because removing from the middle is O(n) for arrays ! btw it is correct but not efficient !
Why did we assume that 0th index has element zero
we aren't, the "L = 0" is just a left pointer the 0 meaning 0 index when we use it with the array like nums[L]
clean af
How can " if nums[r]:" mean that number is not zero?
boolean conversion of number greater than 0
Block of code after If statememt will run only if the condition is True. The condition will be False if it has a value of 0, anything other than 0 is True.
Not zero
U can also write num[r]!=0
@@hellowrld9888thats not what he asked
Can anyone suggest a youtube channel which explain programs in java?
On the last line, you don't need to return anything because the problem says so
Where is the partition though i am confused
No partition is performed. It is a pointer method in which left starts from start index and right, one greater than start index. if R is greater than L, swap is performed else R moves +1
partition is done in quick sort only.
maaaaaaan i failed with this taks on interview 2 weeks ago
which company?
Where the videos that people are talking about. How helpful the videos are. Do you have to pay for it???
void moveZeroes(vector& v) {
int n=v.size();
int next=0;
for(int i=0;i
my approach is accepted but, with 283ms is it worthfull ?
my approach was around 69ms and it only beat 7 % of people. its better to learn an algorithm that works in o(n). Your code worked for 238ms because of o(n)^2 time complexity like mine
How about just moving all the non-zero values to the start and just adding zeroes to the end. Beats 99.48 python users apparently
7:24 bro just made ad for python
they clearly told don't return anything
I just did remove and append like an idiot lol
it says don't return anything lol
lol whoops i missed that part
@@NeetCode I think now you have to
for i = l in range(nums)
// set the remaining elements to zero
// at the index starting from i
// num[i] = 0
But it happens 🤣🙃
well spotted👍