Move Zeros to End — Problem Statement & Solution Guide
Problem Description
Given an array of integers, move all zeros to the end of the array while maintaining the relative order of non-zero elements.
Examples
Input
[0,1,0,3,12]
Output
[1,3,12,0,0]
Explanation: Step-by-step: with input [0,1,0,3,12], we iterate through the array and move all non-zero elements to the front, maintaining their relative order, giving output [1,3,12,0,0]
Input
[4,2,4,0,0,3,0,5,1,0]
Output
[4,2,4,3,5,1,0,0,0,0]
Explanation: Step-by-step: with input [4,2,4,0,0,3,0,5,1,0], we move all zeros to the end while keeping the relative order of non-zero elements, resulting in [4,2,4,3,5,1,0,0,0,0]
Constraints
- 1 <= n <= 10^5
Optimal Approach & Strategy
Maintain a pointer 'lastNonZeroFoundAt'. Iterate array, if element is non-zero, swap it with element at 'lastNonZeroFoundAt' and increment the pointer. Time: O(N), Space: O(1).
Brute Force Approach
Create a new array, copy non-zeros first, then fill the rest with zeros. Space O(N).
Verified Code Solutions
function moveZerosToEnd(nums) { let nonZeroIndex = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] !== 0) { [nums[nonZeroIndex], nums[i]] = [nums[i], nums[nonZeroIndex]]; nonZeroIndex++; } } return nums; }class Solution { public: vector<int> moveZerosToEnd(vector<int>& nums) { int nonZeroIndex = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] != 0) { swap(nums[nonZeroIndex], nums[i]); nonZeroIndex++; } } return nums; } }class Solution { public int[] moveZerosToEnd(int[] nums) { int nonZeroIndex = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != 0) { int temp = nums[nonZeroIndex]; nums[nonZeroIndex] = nums[i]; nums[i] = temp; nonZeroIndex++; } } return nums; } }def move_zeros(arr): return [i for i in arr if i != 0] + [0] * arr.count(0)function moveZerosToEnd(nums) { let nonZeroIndex = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] !== 0) { [nums[nonZeroIndex], nums[i]] = [nums[i], nums[nonZeroIndex]]; nonZeroIndex++; } } return nums; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.