Review the fundamentals: Arrays guide and time complexities.
Move Zeros to End — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Move Zeros to End problem optimally.
O(N)O(1)Problem Description
You are given an array of integers named sequence. Your objective is to modify sequence in-place by relocating all zero values (0) to the end of the array, while strictly preserving the initial relative ordering of all non-zero elements.
The reordering must be executed directly within the original array without allocating a secondary array or additional dynamic memory. The solution must operate with $O(1)$ auxiliary space complexity and process the array in linear time.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Move Zeros to End"
WHY DOES IT MATTER?
The Reader/Writer two-pointer technique is a core primitive for in-place array transformations, filtering, and memory defragmentation without allocating new memory blocks.
OPTIMIZATION CHALLENGE
Achieving $O(N)$ time complexity with $O(1)$ extra space requires avoiding nested loops or array shift operations like splice(), which silently degrade performance to $O(N^2)$.
REAL-WORLD CONNECTION
In operating systems and database storage engines, memory compactors use this exact logic to shift active memory blocks together and aggregate free space into a single contiguous block.
In interviews, explicitly discuss write minimization. Highlighting the difference between unconditional swaps and guarded writes demonstrates senior-level performance awareness.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The 'Move Zeros to End' problem requires in-place array modification while maintaining stability, meaning the original relative order of non-zero elements must remain unchanged. A naive attempt that removes zeros and shifts remaining elements leftwards leads to repeated element shifting, causing an overall $O(N^2)$ time complexity. Allocating a secondary array allows $O(N)$ linear time but violates the strict $O(1)$ auxiliary space constraint. To solve this efficiently, we must process the array in linear time using an optimal in-place state transformation.
Interview Questions on This Problem
Q1How can you minimize the total number of array write operations if the array contains mostly non-zero elements or mostly zero elements?
If using the swap approach, avoid swapping an element with itself when read_index == write_index (e.g., when no zeros have been encountered yet). If using the two-pass overwrite approach, only write zeros from write_index to the end of the array, which performs at most $N$ total writes regardless of zero density.
Q2How does this algorithm relate to the Lomuto partitioning scheme in QuickSort?
It is conceptually identical to Lomuto partitioning, where the pivot condition is element != 0. The array is partitioned into two regions: elements matching the predicate (non-zeros) placed on the left, and elements failing the predicate (zeros) placed on the right, all while maintaining stability for the left partition.
Q3If the input array is extremely large and stored on disk as a data stream, how would you process it with minimal memory overhead?
In a streaming scenario where random access is expensive, process elements sequentially: immediately output non-zero values to the destination stream while keeping a running counter of zeros. Once the input stream ends, write 'zero_count' zeros to the output stream. This achieves $O(N)$ time and $O(1)$ space.
Examples
Input
sequence = [4, 0, -2, 0, 9, 12]
Output
[4, -2, 9, 12, 0, 0]
Explanation: The non-zero elements in order of appearance are 4, -2, 9, and 12. Trailing zeros are placed at the final two positions while maintaining the original sequence of non-zeros.
Input
sequence = [0, 0, 15, 3]
Output
[15, 3, 0, 0]
Explanation: The leading zero values are shifted to the rightmost positions, allowing the non-zero integers 15 and 3 to occupy the initial slots in their original order.
Input
sequence = [7, 8, 11]
Output
[7, 8, 11]
Explanation: The array contains no zero elements; thus, no swaps or shifts are necessary, and the sequence remains intact.
Input
sequence = [0, 0, 0]
Output
[0, 0, 0]
Explanation: Every element in the sequence is zero, so the array configuration stays identical after processing.
Constraints
- 1 <= sequence.length <= 10^5
- -2^31 <= sequence[i] <= 2^31 - 1
- Space Complexity: O(1) auxiliary space (in-place modification)
Optimal Approach & Strategy
Iterate through the array with a fast pointer while maintaining a slow pointer for the next non-zero slot. Swap sequence[slow] and sequence[fast] whenever sequence[fast] is non-zero, then increment slow, placing all non-zeros forward in $O(N)$ time and $O(1)$ space.
Brute Force Approach
Copy all non-zero elements into a separate array in order, then pad the remaining length with zeros, and copy the result back. This takes $O(N)$ time but fails the $O(1)$ extra space constraint by using $O(N)$ auxiliary memory.
Code Solutions
/**
* @param {number[]} sequence
* @return {void} Do not return anything, modify sequence in-place instead.
*/
function moveZeros(sequence) {
if (!sequence || sequence.length === 0) return;
let lastNonZeroIndex = 0;
// First pass: move all non-zero elements to the front
for (let i = 0; i < sequence.length; i++) {
if (sequence[i] !== 0) {
[sequence[lastNonZeroIndex], sequence[i]] = [sequence[i], sequence[lastNonZeroIndex]];
lastNonZeroIndex++;
}
}
// Second pass: fill the remaining positions with zeros
while (lastNonZeroIndex < sequence.length) {
sequence[lastNonZeroIndex] = 0;
lastNonZeroIndex++;
}
}
// Driver code
const sequence = [4, 0, -2, 0, 9, 12];
moveZeros(sequence);
console.log(sequence.join(' '));#include <iostream>
#include <vector>
using namespace std;
void moveZeros(vector<int>& sequence) {
if (sequence.empty()) return;
int lastNonZeroIndex = 0;
// First pass: move all non-zero elements to the front
for (int i = 0; i < sequence.size(); ++i) {
if (sequence[i] != 0) {
swap(sequence[lastNonZeroIndex], sequence[i]);
lastNonZeroIndex++;
}
}
// Second pass: fill the remaining positions with zeros
while (lastNonZeroIndex < sequence.size()) {
sequence[lastNonZeroIndex] = 0;
lastNonZeroIndex++;
}
}
int main() {
vector<int> sequence = {4, 0, -2, 0, 9, 12};
moveZeros(sequence);
for (int i = 0; i < sequence.size(); ++i) {
cout << sequence[i] << (i < sequence.size() - 1 ? " " : "");
}
cout << endl;
return 0;
}import java.util.Arrays;
public class Main {
public static void moveZeros(int[] sequence) {
if (sequence == null || sequence.length == 0) return;
int lastNonZeroIndex = 0;
// First pass: move all non-zero elements to the front
for (int i = 0; i < sequence.length; i++) {
if (sequence[i] != 0) {
int temp = sequence[lastNonZeroIndex];
sequence[lastNonZeroIndex] = sequence[i];
sequence[i] = temp;
lastNonZeroIndex++;
}
}
// Second pass: fill the remaining positions with zeros
while (lastNonZeroIndex < sequence.length) {
sequence[lastNonZeroIndex] = 0;
lastNonZeroIndex++;
}
}
public static void main(String[] args) {
int[] sequence = {4, 0, -2, 0, 9, 12};
moveZeros(sequence);
System.out.println(Arrays.toString(sequence));
}
}def move_zeros(sequence):
"""
Modify the list in-place to move all zeros to the end while
preserving the relative order of non-zero elements.
Args:
sequence (list[int]): The input list of integers.
"""
if not sequence:
return
last_non_zero_index = 0
# First pass: move all non-zero elements to the front
for i in range(len(sequence)):
if sequence[i] != 0:
sequence[last_non_zero_index], sequence[i] = sequence[i], sequence[last_non_zero_index]
last_non_zero_index += 1
# Second pass: fill the remaining positions with zeros
while last_non_zero_index < len(sequence):
sequence[last_non_zero_index] = 0
last_non_zero_index += 1
if __name__ == "__main__":
sequence = [4, 0, -2, 0, 9, 12]
move_zeros(sequence)
print(" ".join(map(str, sequence)))/**
* @param {number[]} sequence
* @return {void} Do not return anything, modify sequence in-place instead.
*/
function moveZeros(sequence) {
if (!sequence || sequence.length === 0) return;
let lastNonZeroIndex = 0;
// First pass: move all non-zero elements to the front
for (let i = 0; i < sequence.length; i++) {
if (sequence[i] !== 0) {
[sequence[lastNonZeroIndex], sequence[i]] = [sequence[i], sequence[lastNonZeroIndex]];
lastNonZeroIndex++;
}
}
// Second pass: fill the remaining positions with zeros
while (lastNonZeroIndex < sequence.length) {
sequence[lastNonZeroIndex] = 0;
lastNonZeroIndex++;
}
}
// Driver code
const sequence = [4, 0, -2, 0, 9, 12];
moveZeros(sequence);
console.log(sequence.join(' '));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.