19. Sort Colors

Medium · Array

Given an array containing only the values 0, 1, and 2 (representing red, white, and blue), sort the array in-place so that objects of the same color are adjacent, with the colors in the order red (0), white (1), and blue (2).

You must solve this problem without using the library's sort function. The array should be modified in-place with O(n) time complexity and O(1) space complexity.

Examples

Example 1
Input: [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: The array is rearranged so all 0s come first, then all 1s, then all 2s.
Example 2
Input: [2, 0, 1]
Output: [0, 1, 2]
Explanation: Each color appears once and is sorted in ascending order.

Constraints