Getting everything ready for you…

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

0s

Practice › Arrays

Sort 0s, 1s and 2s

Medium · Arrays · Asked at Amazon, Microsoft, Adobe, Flipkart, Paytm

The array contains only 0, 1 and 2. Sort it without using a sorting function.

Input

First line: n. Second line: n space-separated integers.

Output

The sorted array, space-separated.

Constraints

Dutch National Flag algorithm: one pass with three pointers (low, mid, high).

Example 1

Input

6
2 0 2 1 1 0

Output

0 0 1 1 2 2

Example 2

Input

3
2 0 1

Output

0 1 2

Hints

  1. Counting how many 0s, 1s and 2s there are already gives an O(n) answer.
  2. One-pass version (Dutch National Flag): low, mid and high pointers. 0 → swap to low, 2 → swap to high, 1 → skip.

Approach

Dutch National Flag keeps three regions: [0, low) holds 0s, [low, mid) holds 1s and (high, n-1] holds 2s. Look at a[mid]: if it's 0, swap it with a[low] and advance both; if it's 1, advance mid; if it's 2, swap it with a[high] and move high left. Don't advance mid in that case, because the swapped-in value hasn't been checked yet.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (a[mid] == 0) swap(a[low++], a[mid++]);
        else if (a[mid] == 1) mid++;
        else swap(a[mid], a[high--]);
    }
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
low, mid, high = 0, 0, n - 1
while mid <= high:
    if a[mid] == 0:
        a[low], a[mid] = a[mid], a[low]
        low += 1
        mid += 1
    elif a[mid] == 1:
        mid += 1
    else:
        a[mid], a[high] = a[high], a[mid]
        high -= 1
print(*a)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int low = 0, mid = 0, high = n - 1;
        while (mid <= high) {
            if (a[mid] == 0) {
                int t = a[low]; a[low++] = a[mid]; a[mid++] = t;
            } else if (a[mid] == 1) {
                mid++;
            } else {
                int t = a[high]; a[high--] = a[mid]; a[mid] = t;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
    }
}

Solve Sort 0s, 1s and 2s online · All practice problems