Sort Colors
The key idea
Treat the array as three growing regions: the 0s on the left, the 2s on the right, and the unsorted middle. One pass with three pointers (
low, mid, high) partitions every value into its region in a single sweep, never needing a second pass or a count.Problem
You are given an array nums of n objects colored red, white, or blue. Sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
The colors are represented by the integers 0, 1, and 2: 0 for red, 1 for white, and 2 for blue.
You must solve this problem without using the library's built-in sort function.
Constraints
n == nums.length1 <= n <= 300nums[i]is either0,1, or2
Examples
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Input: nums = [2,0,1]
Output: [0,1,2]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY