Algorithm
Problem Name: 75. Sort Colors
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.length1 <= n <= 300nums[i]is either0,1, or2.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
Code Examples
#1 Code Example with C Programming
Code -
C Programming
void sortColors(int* nums, int numsSize) {
int l, m, r, k;
l = m = 0;
r = numsSize - 1;
while (m < = r) {
k = nums[m];
if (k < 1) { // red - swap left and middle, then advance both pointers
nums[m] = nums[l];
nums[l] = k;
l ++; m ++;
} else if (k > 1) { // blue - swap right and middle, then shrink right pointer
nums[m] = nums[r];
nums[r] = k;
r --;
} else { // white - advance middle
m ++;
}
}
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, high = nums.size()-1;
for(int i = 0; i < = high;)
if(nums[i] == 0)
swap(nums[i++], nums[low++]);
else if(nums[i] == 2)
swap(nums[i], nums[high--]);
else i++;
}
};
// Shorter.
class Solution {
public:
void sortColors(vector<int>& nums) {
for(int i = 0, j = 0, k = nums.size() - 1; j <= k;)
if(nums[j] == 0) swap(nums[i++], nums[j++]);
else if(nums[j] == 2) swap(nums[j], nums[k--]>;
else j++;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public void sortColors(int[] nums) {
int zeroIdx = 0;
int twoIdx = nums.length - 1;
for (int i = 0; i < = twoIdx; ) {
if (nums[i] == 0 && i != zeroIdx) {
int temp = nums[zeroIdx];
nums[zeroIdx++] = nums[i];
nums[i] = temp;
} else if (nums[i] == 2 && i != twoIdx) {
int temp = nums[twoIdx];
nums[twoIdx--] = nums[i];
nums[i] = temp;
} else {
i++;
}
}
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const sortColors = function(nums) {
let j = 0;
let k = nums.length - 1;
const swap = (a, b) => {
const t = nums[a];
nums[a] = nums[b];
nums[b] = t;
};
for (let i = 0; i < = k; i++) {
if (nums[i] === 2) {
swap(i--, k--);
} else if (nums[i] === 0) {
swap(i, j++);
}
}
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
red, white, blue = 0, 0, len(nums)-1
while white <= blue:
if nums[white] == 0:
nums[red], nums[white] = nums[white], nums[red]
white += 1
red += 1
elif nums[white] == 1:
white += 1
else:
nums[white], nums[blue] = nums[blue], nums[white]
blue -= 1
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _075_SortColors
{
public void SortColors(int[] nums)
{
int lt = 0, gt = nums.Length - 1, i = 0, temp;
while (i < = gt)
{
if (nums[i] == 0)
{
temp = nums[lt];
nums[lt++] = nums[i];
nums[i++] = temp;
}
else if (nums[i] == 2)
{
nums[i] = nums[gt];
nums[gt--] = 2;
}
else
{
i++;
}
}
}
public void SortColors_2(int[] nums)
{
var counts = new int[3] { 0, 0, 0 };
int i, j;
for (i = 0; i < nums.Length; i++)
counts[nums[i]]++;
int index = 0;
for (i = 0; i < 3; i++)
for (j = 0; j < counts[i]; j++)
nums[index++] = i;
}
}
}
Input
Output