Sort the Flag

Difficulty: 1000 3000 ms 128 MB

sorting two-pointers

The array contains only 0s, 1s and 2s. Print it sorted — ideally in ONE pass without a sorting routine (Dutch national flag).

Input: the first line has N; the second line has N values from {0, 1, 2}.

Output: the sorted values.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

6
2 0 1 2 0 1

0 0 1 1 2 2

1
1

1

Read the Editorial