Sort Colors

Medium

Given an array of integers where each integer can be 0, 1, or 2, represent three different 'colors'. Your task is to sort this array in-place such that elements of the same color are adjacent, with the colors in the order of 0, 1, and 2. The function should not return anything; instead, it should arrange the elements of the array so that it is sorted appropriately. This problem is to be solved without using the library's sort function.

Example 1

Input

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

Output

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

Explanation. The array should be arranged so that all 0's are before all 1's and all 1's are before all 2's.

Example 2

Input

[
  2,
  1,
  0
]

Output

[
  0,
  1,
  2
]

Explanation. Simple test with only one occurrence of each number.

Example 3

Input

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

Output

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

Explanation. The input is already sorted, so it should remain unchanged.

Example 4

Input

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

Output

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

Explanation. The array elements need to be reversed from 2, 2, 1, 1, 0, 0 to 0, 0, 1, 1, 2, 2.

Example 5

Input

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

Output

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

Explanation. Mixed elements but still needs to be ordered according to the problem statement.

Follow-up: Can you come up with a one-pass algorithm using only constant extra space?

Constraints:

The input array will only contain the integers 0, 1, and 2. Your solution should strive for linear time complexity O(n) and constant space complexity O(1).

Views: 22

Sort Colors

Solution

Judge

Sort Colors

Discussion (0)

Solution

Judge