Move Zeroes - Leetcode 283 - Python

[@timwebster85]

Thank you for taking the time to do this, much appreciated!

[@PremPal-uy4nm]

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!

[@deckardbarnes6715]

Wish I found this channel before I got this question during my interview

[@abhimalyachowdhury7835]

I absolutely love your approach and explanation.... Please upload more Amazon interview questions..I have interview coming up....

[@hacksbsb]

did you get the offer

[@Cruzylife]

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

[@sawyerburnett8319]

Ugh. I had this so close doing the problem on my own but caught up on some edge cases. Explanation is helpful!

[@bellemcky]

Same

[@dhruva1221]

me too unless i un-pause other youtuber video tutorial for java who said to use pointer for zero;s position

[@karthikraghuraman3352]

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?

[@kvtys]

because we are incrementing both left and right pointers when we encounter a non zero value. So for the example you gave, 1 swaps with itself, 4 swaps with itself, 3 swaps with itself. Then the left pointer is left at 0 and the right pointer moves to 2, which then proceeds to swap those elements and increment. Now left pointer is at 0 (because 0 got swapped), and right pointer is at 1. 1 is now swapped with 0, and the for loop exits.

[@dhruva1221]

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 :)

[@nidhipandey3791]

As a person who is starting dsa with this question, the question seemed impossible until I watched the solution. And the solution, man! It turned out to be a basic logic question. Reminded me of jee advance questions where the most fundamental knowledge is tested

[@VinayakKommana]

same feeling buddy

[@sameer_sah]

If you are confused about where does this patterns fits, read about partition alorithm. Thanks Neetcode.

[@mkum2141]

specifically, lomuto's partition algorithm

[@pl5778]

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

[@MaazKhan-lw6kz]

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}"

[@gremlan6419]

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.

[@ninjaHattoriy]

This did not feel easy at all. But your explanation's brilliant and so is your solution. It took me a few dry runs to understand how it would work for all the cases. Leetcode is hard.

[@user-ft1rj5jh3n]

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!!

[@NeetCode]

I got you fam, I'll upload it tomorrow morning!

[@user-ft1rj5jh3n]

@@NeetCode i love you ❤️

[@atulkumar-bb7vi]

Nice insights of simple algorithm. Thanks!

[@ChaseHatch]

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]

sort doesn’t work. You need to maintain order of non-zeros, which doesn’t necessarily mean sorted ordsr

[@ChaseHatch]

@@MrMinecraftGamer456 the for loop will still work here without the sort

[@ChaseHatch]

@@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]

[@avijitdey992]

@@ChaseHatch bro shut up

[@miglioredroid9446]

Too many functions, you should know how to do it with basic data and structures.

[@jesussepulveda9992]

Thank you for your work neet :D

[@traderviajero]

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!

[@kalyaninagre2148]

your efforts are appreciated !!!!

[@jjhassy]

it frustrates me how simple the solution was

[@shadon_official2510]

This is such an awesome video

[@Kushagra_21]

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 :)

[@shubhanshusingh8529]

#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

[@PremPal-uy4nm]

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]))

[@OlaoluwaJames-Owolabi]

or just do : def moveZeroes(self, nums): for i in range(len(nums)): if nums[i] == 0: nums.pop(i) nums.append(0)

[@Andrypka]

Greet explanation, thanks alot!

[@Ivan-ek6kg]

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?

[@KirHashVerse]

Either you can do this way swapping or the temp one, it depends on you

[@bishowahib2736]

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)

[@NeetCode]

Very clean, but I think removing from the middle of an array is O(n) time complexity. So this would be O(n^2)

[@abhimalyachowdhury7835]

Won't it through an error as list size changed while iteration...

[@anshbhatia1]

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

[@anonymoustv8604]

@@anshbhatia1 what do you mean it won't work for [0,0,1]? It will work

[@subhamthemusicalguy8851]

Thanks a lot for this clear explanation

[@durgeshkudalkar6574]

Really good explanation!

[@PixelPulse168]

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.

[@kvtys]

wrong - if the first element is zero, then the left pointer is not iterated and the right pointer is. if the first element is not zero, then both left and right pointer arr incremented.

[@yashshukla1637]

Problem Introduction The problem involves moving all zeros in an array to the right, while maintaining the relative order of non-zero elements. An initial approach might involve creating two arrays: one for zeros and one for non-zero elements, and then combining them. This solution uses extra memory, so the goal is to achieve this in-place with O(1) extra memory. In-Place Partitioning Concept The problem is similar to partitioning in algorithms like quicksort or quick select, where values are divided in-place based on conditions (zero vs non-zero here). Reversing the way the problem is described (moving non-zeros left) helps conceptualize the solution. The array is essentially treated as two parts: non-zeros to the left and zeros to the right. Algorithm Explanation with Two Pointers Left pointer tracks where the next non-zero value should be placed, and right pointer iterates through the array. When the right pointer encounters a zero, nothing is done. When a non-zero is encountered, it's swapped with the value at the left pointer, and then the left pointer moves to the next position. Step-by-Step Example The process of visiting and partitioning values continues until the entire array is sorted with non-zeros on the left and zeros on the right. This method maintains the relative order of non-zeros and ensures zeros end up on the right. Code Implementation in Python The algorithm uses two pointers starting at the beginning. The right pointer moves through the array, and non-zeros are swapped with the left pointer’s value. Python allows simple swapping with one line, though other languages might require helper functions or temporary variables. After each swap, the left pointer is incremented, while the right pointer moves in each iteration. Efficiency and Practical Applications This algorithm is efficient and relates to many other algorithms like quicksort, making it a useful technique to understand. The solution works as expected, and the video encourages liking, subscribing, and supporting on Patreon.

[@SzSzilard]

I coudln't solve this myself, so thanks a bunch!

[@JustFuguFish]

If you pop the 0 and append a 0 at the end of the list wont work?

[@d3v1n302418]

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

[@ayoubalem865]

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 !

[@sherifessam1560]

Man, you are just great

[@prateek8837]

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; };

[@madeehabalouch6648]

You're Amazing!

[@angryman5517]

Why are you returning? It's clearly mentioned not to return anything

[@LauraWinterisYourMom]

Where is the partition though i am confused

[@KirHashVerse]

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

[@farazahmed7]

partition is done in quick sort only.

[@TURALOWEN]

thank you!

[@diabhattacharya3425]

Why did we assume that 0th index has element zero

[@michaelrosa385]

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]

[@heysisteronion]

@@michaelrosa385so u assume nums[0] is zero

[@parashar1505]

It frustrates me how this solution is still so difficult to reason out!

[@devjitghosh550]

This is a great solution, I have an additional code if anyone wants to learn with basic Knowledge of List Assignment : class Solution: def moveZeroes(self, nums: List[int]) -> None: J=[] for i in nums: if i != 0: J.append(i) for i in range(0,len(J)): nums[i]=J[i] for i in range(len(J),len(nums)): nums[i]=0 return nums Though this code has a very bad Space complexity since there is an extra array J to store, it might help for starters

[@barnoma-soz]

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

[@cherylto5898]

I would also move j+=1 outside the if/else and just write it once.

[@barnoma-soz]

@@cherylto5898 yeahh) it would be better

[@ronsinha21]

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

[@wayne4591]

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

[@james8232]

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

[@clovisstanford6515]

Can anyone suggest a youtube channel which explain programs in java?

[@peskovdev]

LeetCode: Do not return anything, modify nums in-place instead NeetCode: return nums

[@whammie9497]

On the last line, you don't need to return anything because the problem says so

[@timanb2491]

maaaaaaan i failed with this taks on interview 2 weeks ago

[@AryanChaurasia10]

which company?

[@nateo7045]

It's a miracle that this even works lmao

[@tcgys]

7:24 bro just made ad for python

[@saraseghidleab4145]

Where the videos that people are talking about. How helpful the videos are. Do you have to pay for it???

[@closingtheloop2593]

clean af

[@inrmh]

thanks : )

[@hideme420]

my approach is accepted but, with 283ms is it worthfull ?

[@whimsicalkins5585]

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

[@abisheknair3545]

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

[@sairamkandgule8957]

void moveZeroes(vector& v) { int n=v.size(); int next=0; for(int i=0;i

[@prashanthpradeep326]

they clearly told don't return anything

[@vishnu00764]

I just did remove and append like an idiot lol

[@Maaaaars]

it says don't return anything lol

[@NeetCode]

lol whoops i missed that part

[@Maaaaars]

@@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 🤣🙃

[@CostaKazistov]

well spotted👍