Given an array containing only the values 0, 1 and 2, sort it in non-decreasing order (the "Dutch national flag" problem).
Input
Line 1: an integer n.
Line 2: n integers, each 0, 1 or 2.
Output
The sorted array, space-separated.
Sort Colors
Mediumarrayssorting
Examples
Example 1
- Input
6 2 0 2 1 1 0
- Output
0 0 1 1 2 2
Two 0s, two 1s, two 2s.
Example 2
- Input
3 2 1 0
- Output
0 1 2
0 1 2.
Example 3
- Input
1 1
- Output
1
A single value.
Constraints
- 1 <= n <= 10^5
- Each value is 0, 1 or 2.
Hints
Reveal hint 1
You could sort, but with only three values you can just count them.
Reveal hint 2
Output that many 0s, then 1s, then 2s.
Reference solution (spoiler — try it yourself first)
Approach
Count the 0s, 1s and 2s and emit them in order (a three-way partition also works in one pass).
import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
a = d[1:1 + n]
print(' '.join(map(str, sorted(a))))
Bring us the problem, not a perfect specification
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.
- 01Share contextDescribe the workflow, constraint or risk.
- 02Clarify togetherWe identify missing facts and useful options.
- 03Choose a startAgree a focused assessment or delivery step.