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.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]Example 2:
Input: nums = [0]
Output: [0]Constraints:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
Understanding
The base case for this question would be [0], and it keeps [0]. 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.
Approach
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.
One-pointer approach
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,
if given nums=[1,0,2], then nums[0] is 1 and nums[2]is 2.
Also, we can assign a value on that index with = .
In the above example, nums[1]=3 will enable to change the value in index 1, so nums will be changed to [1,3,2].
Here is the code after learning lists of Python.
class Solution(object):
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).
Complexity
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.
Remark
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
