Description:
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.
Examples:
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]Solution in Python:
Python
from typing import List
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# Initialize pointers for the current element (mid),
# the boundary for zeros (low), and the boundary for twos (high).
low, mid, high = 0, 0, len(nums) - 1
# Process elements in the array
while mid <= high:
if nums[mid] == 0:
# Swap the mid element with the low element
nums[low], nums[mid] = nums[mid], nums[low]
# Increment both low and mid pointers
low += 1
mid += 1
elif nums[mid] == 1:
# If the element is 1, just move the mid pointer
mid += 1
else:
# Swap the mid element with the high element
nums[high], nums[mid] = nums[mid], nums[high]
# Decrement the high pointer
high -= 1Explanation:
- Initialization:
low: Pointer to the boundary of the next position for 0.mid: Pointer to the current element being processed.high: Pointer to the boundary of the next position for 2.
- Traversal:
- The algorithm processes the elements while
mid <= high.
- The algorithm processes the elements while
- Conditions:
- If
nums[mid] == 0:- Swap the element at
midwith the element atlow. - Increment both
lowandmidbecause the element atmidis now sorted.
- Swap the element at
- If
nums[mid] == 1:- Move the
midpointer because 1 is already in the correct position.
- Move the
- If
nums[mid] == 2:- Swap the element at
midwith the element athigh. - Decrement
highbecause the element atmidneeds to be checked again.
- Swap the element at
- If
This approach ensures that all 0s are moved to the beginning, all 2s to the end, and all 1s remain in the middle in a single pass with constant space complexity.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
// Initialize pointers for the current element (mid),
// the boundary for zeros (low), and the boundary for twos (high).
let low = 0;
let mid = 0;
let high = nums.length - 1;
// Process elements in the array
while (mid <= high) {
if (nums[mid] === 0) {
// Swap the mid element with the low element
[nums[low], nums[mid]] = [nums[mid], nums[low]];
// Increment both low and mid pointers
low++;
mid++;
} else if (nums[mid] === 1) {
// If the element is 1, just move the mid pointer
mid++;
} else {
// Swap the mid element with the high element
[nums[high], nums[mid]] = [nums[mid], nums[high]];
// Decrement the high pointer
high--;
}
}
};Solution in Java:
Java
class Solution {
public void sortColors(int[] nums) {
// Initialize pointers for the current element (mid),
// the boundary for zeros (low), and the boundary for twos (high).
int low = 0;
int mid = 0;
int high = nums.length - 1;
// Process elements in the array
while (mid <= high) {
if (nums[mid] == 0) {
// Swap the mid element with the low element
swap(nums, low, mid);
// Increment both low and mid pointers
low++;
mid++;
} else if (nums[mid] == 1) {
// If the element is 1, just move the mid pointer
mid++;
} else {
// Swap the mid element with the high element
swap(nums, mid, high);
// Decrement the high pointer
high--;
}
}
}
// Helper method to swap elements in the array
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}Solution in C#:
C#
public class Solution {
public void SortColors(int[] nums) {
// Initialize pointers for the current element (mid),
// the boundary for zeros (low), and the boundary for twos (high).
int low = 0;
int mid = 0;
int high = nums.Length - 1;
// Process elements in the array
while (mid <= high) {
if (nums[mid] == 0) {
// Swap the mid element with the low element
Swap(nums, low, mid);
// Increment both low and mid pointers
low++;
mid++;
} else if (nums[mid] == 1) {
// If the element is 1, just move the mid pointer
mid++;
} else {
// Swap the mid element with the high element
Swap(nums, mid, high);
// Decrement the high pointer
high--;
}
}
}
// Helper method to swap elements in the array
private void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}