Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

5
0 1 0 3 12

Output

1 3 12 0 0

Example 2

Input

1
0

Output

0

Hints

  1. Copy the non-zero elements forward in their original order.
  2. 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);
    }
}

Solve Move Zeros to End online · All practice problems