Move Zeroes - Leetcode 283 - Python
Vložit
- čas přidán 2. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ 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/move-ze...
0:00 - Read the problem
3:00 - Drawing Explanation
6:36 - Coding Explanation
leetcode 283
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#partition #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Thank you for taking the time to do this, much appreciated!
I absolutely love your approach and explanation.... Please upload more Amazon interview questions..I have interview coming up....
did you get the offer
Wish I found this channel before I got this question during my interview
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!
Nice insights of simple algorithm. Thanks!
Thank you for your work neet :D
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
your efforts are appreciated !!!!
Thanks a lot for this clear explanation
Really good explanation!
This is such an awesome video
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;
};
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 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.
Man, you are just great
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 , 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 :)
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
You're Amazing!
thank you!
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 ❤️
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}"
I coudln't solve this myself, so thanks a bunch!
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.
thanks : )
#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
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)
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.
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
clean af
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?
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
maaaaaaan i failed with this taks on interview 2 weeks ago
which company?
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
On the last line, you don't need to return anything because the problem says so
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
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 !
it frustrates me how simple the solution was
Why are you returning? It's clearly mentioned not to return anything
7:24 bro just made ad for python
Why did we assume that 0th index has element zero
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.
they clearly told don't return anything
I just did remove and append like an idiot lol
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
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
LeetCode: Do not return anything, modify nums in-place instead
NeetCode: return nums
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👍
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