Move Zeroes
Asked at Meta, Microsoft, Apple, Walmart
Problem
Given an integer array nums, move all 0s to the end while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
Use two pointers: a slow pointer (write position) and a fast pointer (scanner). The slow pointer tracks where the next non-zero element should go.
Visual walkthrough for [0,1,0,3,12]:
slow=0, fast=0. nums[fast]=0, skip.
fast=1. nums[fast]=1 != 0. Swap nums[slow] and nums[fast]. Array: [1,0,0,3,12]. slow=1.
fast=2. nums[fast]=0, skip.
fast=3. nums[fast]=3 != 0. Swap nums[slow] and nums[fast]. Array: [1,3,0,0,12]. slow=2.
fast=4. nums[fast]=12 != 0. Swap nums[slow] and nums[fast]. Array: [1,3,12,0,0]. slow=3.
Result: [1,3,12,0,0].
Why swap instead of shift: shifting all elements right is O(n^2). Swapping two elements is O(1) per operation. Total: O(n).
Alternative two-pointer approach: slow pointer only advances when a non-zero is found. Fast pointer always advances. When both are at non-zeros, they might be the same element, but that is harmless.
Edge cases: all zeroes (array unchanged), no zeroes (array unchanged), single element (unchanged).
Optimal Approach
Step 1: Initialize slow = 0.
Step 2: Iterate fast from 0 to n-1:
- If nums[fast] != 0:
- Swap nums[slow] and nums[fast]
- Increment slow
Step 3: The array is modified in-place.
The slow pointer always points to the position where the next non-zero should go. Everything before slow is non-zero. Everything after fast has not been examined yet.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Using extra space by creating a new array. The problem explicitly requires in-place modification.
Shifting all elements right when a zero is found. That is O(n^2). Use two pointers for O(n).
Not preserving relative order of non-zero elements. The relative order must stay the same, so you cannot just swap zeroes to the end arbitrarily.
Forgetting that the slow pointer should only advance when a non-zero swap occurs. If you advance it unconditionally, you overwrite elements.
Confusing this with removing zeroes entirely. The array length stays the same, zeroes just move to the end.
Solution Code
def moveZeroes(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1Frequently Asked Questions
What is the Move Zeroes problem?
Given an integer array nums, move all 0s to the end while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.
How do you solve Move Zeroes?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Move Zeroes?
Move Zeroes is asked at Meta, Microsoft, Apple, Walmart. It is a easy difficulty problem.
What are common mistakes on Move Zeroes?
- Using extra space by creating a new array. The problem explicitly requires in-place modification.
- Shifting all elements right when a zero is found. That is `O(n^2)`. Use two pointers for `O(n)`.
- Not preserving relative order of non-zero elements. The relative order must stay the same, so you cannot just swap zeroes to the end arbitrarily.
- Forgetting that the slow pointer should only advance when a non-zero swap occurs. If you advance it unconditionally, you overwrite elements.
- Confusing this with removing zeroes entirely. The array length stays the same, zeroes just move to the end.