Sort Colors

mediumSave

ArraySortingTwo Pointers

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,
  1,
  0
]

Output

[0, 1, 2]

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

Example 2

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 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: 3