Practice › Arrays
Move Zeros to End
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Move all zeros to the end of the array while keeping the relative order of the non-zero elements.
Input
First line: n. Second line: n space-separated integers.
Output
The array after moving the zeros, space-separated.
Constraints
- 1 ≤ n ≤ 10^5
Example 1
Input
5 0 1 0 3 12
Output
1 3 12 0 0
Example 2
Input
1 0
Output
0
Hints
- Copy the non-zero elements forward in their original order.
- Keep a pointer to the next free slot; after the scan, fill the remaining slots with zeros.
Approach
Walk the array with a write pointer k. Every non-zero element is written to a[k++], which keeps their relative order. Everything from k to the end is then set to 0. (Swapping a[i] with a[k] does both steps in one pass.)
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
int k = 0;
for (int i = 0; i < n; i++)
if (a[i] != 0) swap(a[i], a[k++]);
for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
n = int(data[0])
a = data[1 : n + 1]
non_zero = [x for x in a if int(x) != 0]
print(*(non_zero + ["0"] * (n - len(non_zero))))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
int k = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
if (x != 0) a[k++] = x;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
System.out.println(sb);
}
}