Dutch National Flag (Sort Colors)

Medium·Tagsarraytwo-pointerssorting

Problem Statement

Given an array containing only 0s, 1s, and 2s, sort the array in-place so that objects of the same color are adjacent, with the colors in the order 0, 1, and 2. You must solve this problem without using the library's built-in sort function. Note: This is known as the Dutch National Flag problem, proposed by Edsger W. Dijkstra, because the values 0, 1, and 2 can be thought of as the red, white, and blue colors of the Dutch flag.

Examples

Example 1

Input

arr: [1, 0, 2, 1, 0]

Output

"[0, 0, 1, 1, 2]"

Why

Sorted in place, the two 0s come first, the two 1s follow, and the single 2 comes last, which is the required order of 0, 1, then 2.

Example 2

Input

arr: [2, 2, 0, 1, 2, 0]

Output

"[0, 0, 1, 2, 2, 2]"

Why

The two 0s move to the front, the lone 1 sits in the middle, and the three 2s gather at the end, all rearranged within the original array.

Constraints

•1 <= arr.length <= 1000
•arr[i] is either 0, 1, or 2.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

You can solve this with three pointers: one for the 0s boundary, one for the 2s boundary, and one to iterate through the array.

Hint 2

Let `low` point to the start, `high` point to the end, and `mid` be the iterator.

Hint 3

If `arr[mid] == 0`, swap it with `arr[low]`. If `arr[mid] == 2`, swap it with `arr[high]`. What should you do if it equals 1?