Sort Colors (Dutch National Flag)

mediumArrays & Hashing+20 XPTime limit 2s

The array holds only 0, 1 and 2 (think red, white, blue). Sort it so all 0s come first, then the 1s, then the 2s.

Input:

line 1: n
line 2: n values, each 0, 1 or 2

Output: the sorted array on one line.

Constraints: 1 ≤ n ≤ 10⁵.

Challenge: a library sort or counting works — but try the one-pass, in-place Dutch National Flag algorithm with three pointers (low, mid, high).

Sample input 1

6
2 0 2 1 1 0

Sample output 1

0 0 1 1 2 2

Sample input 2

3
2 0 1

Sample output 2

0 1 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…