Move Zeros to the End of an Array

53.9k
0

Problem Statement

Given an integer array nums, move every 0 to the end of the array.

Relative order of all non-zero values must remain unchanged.

The final array contains all non-zero values first in original order, followed by all zeros.

Example 1

Input: nums = [0, 1, 0, 3, 12]

Output: [1, 3, 12, 0, 0]

Explanation: Non-zero values 1, 3, and 12 keep original order. Both zeros move to the end.

Example 2

Input: nums = [0, 0, 1]

Output: [1, 0, 0]

Explanation: Value 1 moves to the front. Two zeros occupy the last two positions.

Example 3

Input: nums = [4, 5, 0, 0, 6]

Output: [4, 5, 6, 0, 0]

Explanation: Non-zero values 4, 5, and 6 keep original order. Zeros shift to the end.

Brute Force Approach

A helper array makes order preservation straightforward.

First, every non-zero value is copied from left to right. Since the values are collected in their original traversal order, their relative order remains unchanged.

Afterward, enough zeroes are added to restore the original array length, and the completed arrangement is copied back into nums.

Algorithm

  • Create an empty helper array temp, which will store the elements in their required final order without modifying nums during traversal.

  • Traverse nums from left to right and append every non-zero value to temp. Since they are added in traversal order, their relative order remains unchanged.

  • Append 0s until temp contains the same number of elements as nums, filling the positions left after collecting all non-zero values.

  • Copy every value from temp back into the corresponding position of nums so that the original array receives the rearranged order.

Dry Run

Move Zeroes to End Brute Force Dry Run.png

Move Zeroes to End Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
vector<int> temp;
/*
* Collect non-zero values first
* to preserve their original order.
*/
for (int num : nums) {
if (num != 0) {
temp.push_back(num);
}
}
/*
* Fill the remaining positions
* with zeroes.
*/
while (temp.size() < n) {
temp.push_back(0);
}
// Copy the final arrangement back into nums.
for (int index = 0; index < n; index++) {
nums[index] = temp[index];
}
}
};
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
Solution solution;
solution.moveZeroes(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Linear traversals collect the non-zero values, append the required zeroes, and copy the final arrangement back.

Space Complexity: O(N), because the helper array may store all N elements.

Better Approach

The helper array can be removed by treating the front part of nums as the destination for non-zero values.

A variable insertPosition marks the next index where a non-zero value should be placed. Every non-zero value is written there, and the position advances.

Once all non-zero values have been compacted at the front, the remaining positions are filled with zeroes.

Algorithm

  • Initialize insertPosition with 0, where it represents the next position at which a non-zero value should be placed.

  • Traverse nums from left to right so that non-zero values are processed in their original order.

  • Whenever nums[index] is non-zero, write it at nums[insertPosition] and increment insertPosition. This compacts all non-zero values toward the beginning without changing their relative order.

  • After the traversal, every position before insertPosition contains the required non-zero values.

  • Fill all positions from insertPosition to the last index with 0, since these are the positions remaining after the non-zero section.

Dry Run

Move Zeroes to End Better Approach Dry Run.png

Move Zeroes to End Better Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int insertPosition = 0;
/*
* Place non-zero values at the front
* in the same order they appear.
*/
for (int index = 0; index < n; index++) {
// Only non-zero values belong in the front section.
if (nums[index] != 0) {
nums[insertPosition] = nums[index];
insertPosition++;
}
}
/*
* Positions left after compaction
* must contain zeroes.
*/
while (insertPosition < n) {
nums[insertPosition] = 0;
insertPosition++;
}
}
};
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
Solution solution;
solution.moveZeroes(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. One traversal places non-zero values, and another traversal fills the remaining positions with zeroes.

Space Complexity: O(1), because the array is modified using only insertPosition and loop variables.

Optimal Approach

The array can be rearranged during a single traversal using two pointers.

zeroPosition marks the next front position that should contain a non-zero value. The current pointer scans the array from left to right.

Whenever a non-zero value appears, it is swapped with the value at zeroPosition. Since non-zero values are processed from left to right, their relative order remains unchanged. Zeroes are gradually moved behind the non-zero section.

Algorithm

  • Initialize zeroPosition with 0, where it represents the next front position that should contain a non-zero value.

  • Traverse the array from left to right using current, allowing non-zero values to be handled in their original order.

  • If nums[current] is non-zero, swap it with nums[zeroPosition]. When zeros have already been encountered, this places the current non-zero value into the earliest available position before them.

  • Increment zeroPosition after every non-zero value, so it continues to point to the next position available for another non-zero element.

  • If the current value is 0, leave it unchanged. A later non-zero value will automatically swap into that position when required.

  • After the traversal, the non-zero values appear first in their original order, while all zeros are pushed to the end.

Dry Run

Move Zeroes to End Optimal Dry Run.png

Move Zeroes to End Optimal Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int zeroPosition = 0;
for (int current = 0; current < n; current++) {
/*
* A non-zero value belongs at the
* next available front position.
*/
if (nums[current] != 0) {
swap(nums[current], nums[zeroPosition]);
zeroPosition++;
}
}
}
};
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
Solution solution;
solution.moveZeroes(nums);
for (int num : nums) {
cout << num << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. A single traversal processes every element exactly once.

Space Complexity: O(1), because only the two pointer variables require auxiliary storage.

Interview follow-up Questions

The problem requires a stable rearrangement. A sequence such as [4, 0, 2] must become [4, 2, 0], not [2, 4, 0].

ArraysTwo Pointer

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.5k
Comments0