Given an array nums
with 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.
We will use the integers 0
, 1
, and 2
to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
Example 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output: [0,1,2]
Constraints:
n == nums.length
1 <= n <= 300
nums[i]
is either 0
, 1
, or 2
.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
This problem requires sorting an array of integers representing colors (0 for red, 1 for white, 2 for blue) in-place, without using a sorting function. The optimal solution uses a three-pointer approach for a single-pass, constant-space solution.
We employ three pointers:
i
: Tracks the index of the last '0' (red) encountered. It starts at -1 (no '0's initially).j
: Tracks the index of the first '2' (blue) encountered. It starts at n
(the array's length – beyond the last element).k
: Iterates through the array, examining each element. It starts at 0.The algorithm proceeds as follows:
Iteration: The while k < j
loop iterates through the array. This condition ensures we don't go past the j
pointer (which marks the beginning of unsorted '2's).
Case 1: nums[k] == 0
(Red): If we find a '0', it needs to be moved to the left (before the '1's and '2's). We swap nums[k]
with nums[i+1]
, effectively placing the '0' at the correct position. Both i
and k
are incremented because we've placed a '0' correctly and need to check the next element.
Case 2: nums[k] == 2
(Blue): If we find a '2', it needs to be moved to the right (after the '0's and '1's). We swap nums[k]
with nums[j-1]
, moving the '2' to the right end of the unsorted region. Only j
is decremented because k
remains unchanged; we need to check the element that swapped into position k
.
Case 3: nums[k] == 1
(White): If we find a '1', it's already in its correct sorted position (between the '0's and '2's). Thus, only k
is incremented.
After the loop finishes, the array will be sorted in the order 0, 1, 2.
The code examples in various languages are provided in the original response. They all implement the same three-pointer algorithm, showcasing its concise and efficient nature. The swap
function (present in some examples) simply exchanges the values at two array indices.
This three-pointer technique cleverly avoids nested loops, resulting in an optimal solution that is both efficient and elegant.