Learning Python with Interview Questions 4. Move Zeroes
Question. Move Zeroes (LC 283)
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.
Input: nums = [0,1,0,3,12]
Input: nums = 
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
The base case for this question would be , and it keeps . Some other cases are [0, 0, 1] and will be changed to [1, 0, 0]. If the given array doesn’t contain zeros such as [9, 1, 3], it keeps the original order.
How to move zeros while keeping the order of non-zero integers? The easiest way is that copy the integer to another empty array and filled out the zeros when the loop is done. However, the given question asked to in-place way rather than copying.
We need to keep track of how many zeros are there as well as the last index of non-zero numbers while looping through the list.
- Keep track of the last index of non-zero integer.
in [2, 0, 3] case, we can keep checking if the number is not zero.
Let’s say ‘nonZero’ starts from index zero, and if the current element is not zero, nums[nonZero] will be replaced by the current element. Otherwise, the loop skips the current element.
I can think of this ‘nonZero’ as a slow pointer.
Writing code with Python
One confusing part was getting the index position with Python. Python lists use
array[i] style to access that element. For example,
nums is 1 and
Also, we can assign a value on that index with
In the above example,
nums=3 will enable to change the value in index 1, so
nums will be changed to
Here is the code after learning lists of Python.
def moveZeroes(self, nums):
slow = 0
for i in nums:
if i != 0:
nums[slow] = i
slow += 1
for i in range(slow, len(nums)):
nums[i] = 0
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
The above solution uses 2 paths which means using 2 for loops for the solution. But the time complexity is still O(n).
Time: The solution went to through a whole array once, and another loop once in the worst case. It would be 2n that will be amortized to O(n). So it will take linear time.
Space: O(1) — Just constant space is being used.
Move Zeros is a pretty short question but asked by many big companies. For example, if two questions are expected to be asked during the 40 minutes tech interview, Move zeros can be used as a warm-up question. So it’s important to answer this question as quickly enough and move on to the next question. :D