Move Zeroes
EasyPrompt
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
Follow up: Could you minimize the total number of operations done?
Approaches
3 approaches with complexity analysis and trade-offs.
Use an additional array to store non-zero elements first, then fill remaining positions with zeros.
Algorithm
- Create new array of same size as input
- Copy non-zero elements maintaining order
- Fill remaining positions with zeros
- Copy back to original array
Walkthrough
This approach uses an extra array to solve the problem in two passes:
- Create a new array of the same size as input
- Iterate through the input array and copy non-zero elements to the new array
- Fill remaining positions with zeros
- Copy back elements to original array
public void moveZeroes(int[] nums) { int[] result = new int[nums.length]; int nonZeroIndex = 0; // First pass: copy non-zero elements for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { result[nonZeroIndex++] = nums[i]; } } // Fill remaining positions with zeros while (nonZeroIndex < nums.length) { result[nonZeroIndex++] = 0; } // Copy back to original array for (int i = 0; i < nums.length; i++) { nums[i] = result[i]; }}Complexity
Time
O(n) where n is the length of the array - requires two passes through the array
Space
O(n) where n is the length of the array - requires extra array of same size
Trade-offs
Pros
Simple to understand and implement
Maintains relative order of non-zero elements
Only requires two passes through the array
Cons
Uses extra space
Not in-place as required by the problem
Requires copying elements back to original array
Use two pointers to track the position for next non-zero element and current element, swapping when necessary.
Algorithm
- Initialize lastNonZeroFoundAt = 0
- Iterate through array with cur pointer
- When non-zero element found, swap with lastNonZeroFoundAt position
- Increment lastNonZeroFoundAt
Walkthrough
This approach uses two pointers to solve the problem in a single pass:
- Initialize two pointers: lastNonZeroFoundAt and cur
- As we iterate cur pointer, whenever we find a non-zero element, we swap it with the element at lastNonZeroFoundAt
- Increment lastNonZeroFoundAt after each swap
public void moveZeroes(int[] nums) { int lastNonZeroFoundAt = 0; // Move all non-zero elements to front for (int cur = 0; cur < nums.length; cur++) { if (nums[cur] != 0) { int temp = nums[lastNonZeroFoundAt]; nums[lastNonZeroFoundAt] = nums[cur]; nums[cur] = temp; lastNonZeroFoundAt++; } }}Complexity
Time
O(n) where n is the length of the array - single pass through the array
Space
O(1) - only uses two pointers regardless of input size
Trade-offs
Pros
In-place solution - no extra space needed
Single pass through the array
Maintains relative order of non-zero elements
Minimal number of operations
Cons
Performs unnecessary swaps when elements are already in correct position
Use two pointers but optimize by avoiding unnecessary swaps when elements are already in correct position.
Algorithm
- Initialize nonZeroPos = 0
- Iterate through array
- When non-zero element found, move it to nonZeroPos if needed
- Increment nonZeroPos
Walkthrough
This approach optimizes the two pointers solution by only moving elements when necessary:
- Use two pointers: nonZeroPos and cur
- nonZeroPos tracks where next non-zero element should go
- Only move elements when they are out of position
- Fill remaining positions with zeros
public void moveZeroes(int[] nums) { int nonZeroPos = 0; // Move all non-zero elements to front for (int cur = 0; cur < nums.length; cur++) { if (nums[cur] != 0) { if (cur != nonZeroPos) { nums[nonZeroPos] = nums[cur]; nums[cur] = 0; } nonZeroPos++; } }}Complexity
Time
O(n) where n is the length of the array - single pass through the array
Space
O(1) - only uses two pointers regardless of input size
Trade-offs
Pros
In-place solution - no extra space needed
Single pass through the array
Maintains relative order of non-zero elements
Minimizes number of operations by avoiding unnecessary swaps
Most efficient solution possible for this problem
Cons
Slightly more complex logic than basic two pointers approach
Solutions
Solution
class Solution { public void moveZeroes ( int [] nums ) { int i = - 1 , n = nums . length ; for ( int j = 0 ; j < n ; ++ j ) { if ( nums [ j ] != 0 ) { int t = nums [++ i ]; nums [ i ] = nums [ j ]; nums [ j ] = t ; } } } }/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var moveZeroes = function (nums) { let i = -1; for (let j = 0; j < nums.length; ++j) { if (nums[j]) { const t = nums[++i]; nums[i] = nums[j]; nums[j] = t; } } };class Solution {public: void moveZeroes(vector<int> &nums) { int i = -1, n = nums.size(); for (int j = 0; j < n; ++j) { if (nums[j]) { swap(nums[++i], nums[j]); } } }};class Solution: def moveZeroes(self, nums: List[int]) -> None: i = - 1 for j, x in enumerate(nums): if x: i += 1 nums[i], nums[j] = nums[j], nums[i]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.