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