Move all Zeros to the end of the array
Given an integer array nums, move all 0's to the end of the array while maintaining the relative order of the non-zero elements.
Example 1
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: All non-zeros [1,3,12] keep their order, zeros move to the end.
Example 2
Input: nums = [0, 0, 1]
Output: [1, 0, 0]
Constraints:
-
1 <= nums.length <= 10^5
-
-10^9 <= nums[i] <= 10^9
Brute Force Approach (Using an Extra Array)
When solving problems like Move all zeros to the end of an array, the brute force idea is often the simplest way to start.
It may not be the most optimal, but it's an excellent first step toward understanding the problem's mechanics.
Idea : The basic idea is straightforward:
-
Create a new temporary array.
-
Copy all non-zero elements into it in the same order they appear.
-
After that, fill the remaining positions with zeros.
-
Finally, copy everything back into the original array.
This ensures that:
-
All non-zero values maintain their relative order (stability).
-
All zeros move neatly to the end.
-
The logic is easy to visualize and debug.
#include <iostream>
#include <vector>
using namespace std;
void moveZeroesBruteForce(vector<int>& nums) {
int n = nums.size();
vector<int> temp(n);
int index = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
temp[index++] = nums[i];
}
}
while (index < n) {
temp[index++] = 0;
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroesBruteForce(nums);
cout << "After moving zeroes: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
public class MoveZeroesBruteForce {
static void moveZeroesBruteForce(int[] nums) {
int n = nums.length;
int[] temp = new int[n];
int index = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
temp[index++] = nums[i];
}
}
while (index < n) {
temp[index++] = 0;
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroesBruteForce(nums);
System.out.print("After moving zeroes: ");
for (int num : nums) {
System.out.print(num + " ");
}
}
}
using System;
public class MoveZeroes {
public static void MoveZeroesBruteForce(int[] nums) {
int n = nums.Length;
int[] temp = new int[n];
int index = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
temp[index++] = nums[i];
}
}
while (index < n) {
temp[index++] = 0;
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
public static void Main() {
int[] nums = {0, 1, 0, 3, 12};
MoveZeroesBruteForce(nums);
Console.Write("After moving zeroes: ");
foreach (int num in nums) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
def move_zeroes_brute_force(nums):
n = len(nums)
temp = [0] * n
index = 0
for i in range(n):
if nums[i] != 0:
temp[index] = nums[i]
index += 1
while index < n:
temp[index] = 0
index += 1
for i in range(n):
nums[i] = temp[i]
if __name__ == "__main__":
nums = [0, 1, 0, 3, 12]
move_zeroes_brute_force(nums)
print("After moving zeroes:", nums)
After moving zeroes: 1 3 12 0 0
Complexity Analysis
- Time Complexity O(n) — Each element is visited once and copied once
- Space Complexity O(n) — Because we use a temporary array
Better Approach: Shifting In-Place (with One Extra Pass)
After understanding the brute force method, the next step is to optimize space usage. The idea here is simple: instead of creating a new array, we shift all non-zero elements in-place toward the beginning of the same array then fill the rest with zeros.
This approach eliminates the need for extra memory while still keeping the logic easy to follow.
-
Maintain a pointer index that always indicates the next position where a non-zero should go.
-
Traverse the array from start to end:
-
Whenever you find a non-zero, place it at nums[index] and increment index.
-
Ignore zeros during this phase — they’ll be handled later.
-
-
Once the traversal is done, fill the rest of the array with zeros, starting from index to the end.
#include <iostream>
#include <vector>
using namespace std;
void moveZeroesBetter(vector<int>& nums) {
int index = 0;
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
while (index < nums.size()) {
nums[index++] = 0;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroesBetter(nums);
cout << "After moving zeroes: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
public class MoveZeroesBetter {
public static void moveZeroesBetter(int[] nums) {
int index = 0;
if (num != 0) {
nums[index++] = num;
}
}
while (index < nums.length) {
nums[index++] = 0;
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroesBetter(nums);
System.out.print("After moving zeroes: ");
for (int num : nums) {
System.out.print(num + " ");
}
}
}
using System;
public class MoveZeroesBetter {
public static void MoveZeroesBetterMethod(int[] nums) {
int index = 0;
foreach (int num in nums) {
if (num != 0) {
nums[index++] = num;
}
}
while (index < nums.Length) {
nums[index++] = 0;
}
}
public static void Main() {
int[] nums = {0, 1, 0, 3, 12};
MoveZeroesBetterMethod(nums);
Console.Write("After moving zeroes: ");
foreach (int num in nums) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
def move_zeroes_better(nums):
index = 0
for num in nums:
if num != 0:
nums[index] = num
index += 1
nums[index] = 0
index += 1
if __name__ == "__main__":
nums = [0, 1, 0, 3, 12]
move_zeroes_better(nums)
print("After moving zeroes:", nums)
After moving zeroes: 1 3 12 0 0
Complexity Analysis
- Time Complexity O(n), Two linear passes: one to rearrange, one to fill zeros
- Space Complexity O(1), In-place, no extra array required
Optimal Approach: Two-Pointer Swap (Single Pass)
This is the most efficient and elegant solution for moving all zeros to the end of an array without losing the order of non-zero elements and doing it in just one pass.
The goal is to bring all non-zero elements to the front as we traverse the array, while zeros automatically fall toward the back.
To do that, we use two pointers:
-
slow : marks the position where the next non-zero should be placed.
-
fast : scans through every element in the array.
At each step:
-
If nums[fast] != 0, we swap nums[slow] and nums[fast], then increment slow.
-
This ensures that all non-zero elements are compacted toward the beginning, maintaining their relative order.
By the time we finish traversing, all zeros are automatically at the end.
Step-by-Step Example
nums = [0, 1, 0, 3, 12]
| Step | fast | slow | Action | Result |
|---|---|---|---|---|
| 0 | 0 | 0 | nums[0] = 0 : skip | [0, 1, 0, 3, 12] |
| 1 | 1 | 0 | nums[1] = 1 : swap(nums[1], nums[0]) -> slow++ | [1, 0, 0, 3, 12] |
| 2 | 2 | 1 | nums[2] = 0 : skip | [1, 0, 0, 3, 12] |
| 3 | 3 | 1 | nums[3] = 3 : swap(nums[3], nums[1]) -> slow++ | [1, 3, 0, 0, 12] |
| 4 | 4 | 2 | nums[4] = 12 : swap(nums[4], nums[2]) -> slow++ | [1, 3, 12, 0, 0] |
#include <iostream>
#include <vector>
using namespace std;
void moveZeroesOptimal(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroesOptimal(nums);
cout << "After moving zeroes: ";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
public class MoveZeroesOptimal {
static void moveZeroesOptimal(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroesOptimal(nums);
System.out.print("After moving zeroes: ");
for (int num : nums) {
System.out.print(num + " ");
}
}
}
using System;
public class MoveZeroesOptimal {
public static void MoveZeroesOptimalMethod(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.Length; fast++) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}
public static void Main() {
int[] nums = {0, 1, 0, 3, 12};
MoveZeroesOptimalMethod(nums);
Console.Write("After moving zeroes: ");
foreach (int num in nums) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
def move_zeroes_optimal(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
if __name__ == "__main__":
nums = [0, 1, 0, 3, 12]
move_zeroes_optimal(nums)
print("After moving zeroes:", nums)
After moving zeroes: 1 3 12 0 0
Complexity Analysis
- Time Complexity O(n) Single linear scan through the array
- Space Complexity O(1) In-place; only uses two pointers
Complexity Comparison of All Approaches
| Approach | Time | Space | Passes | Notes |
|---|---|---|---|---|
| Brute Force (Extra Array) | O(n) | O(n) | 2 | Simple, easy to start |
| Better (In-Place, Extra Pass) | O(n) | O(1) | 2 | Memory-efficient |
| Optimal (Two Pointers) | O(n) | O(1) | 1 | Best overall performance |