🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to sort an array of integers that contains only the values 0
, 1
, and 2
. The goal is to arrange the elements such that all the 0
s come first, followed by all the 1
s, and then all the 2
s, in linear time.
Intuition
The task can be solved using a counting approach where we first count the occurrences of each value (0
, 1
, and 2
), and then overwrite the original array using these counts. This method ensures that the array is sorted in a single pass after counting.
Approach
- Counting Phase: Traverse the array and maintain a count of
0
s,1
s, and2
s. - Overwriting Phase: Iterate through the array again and overwrite it with the correct number of
0
s, followed by1
s, and then2
s based on the counts from the first phase. - This approach ensures the sorting is done in linear time, as each element is processed a constant number of times.
Complexity
Time Complexity:
O(n) - where n
is the length of the array. We traverse the array twice: once for counting and once for overwriting.
Space Complexity:
O(1) - We only use a fixed amount of extra space for the count array, making this approach very space-efficient.
Code
C++
class Solution {
public:
void sortColors(vector& nums) {
int count[3] = {0, 0, 0};
for (int i = 0; i < nums.size(); i++) {
count[nums[i]]++;
}
int idx = 0;
for (int color = 0; color < 3; color++) {
for (int j = 0; j < count[color]; j++) {
nums[idx] = color;
idx++;
}
}
}
};
Python
class Solution:
def sortColors(self, nums: List[int]) -> None:
count = {0: 0, 1: 0, 2: 0}
for num in nums:
count[num] += 1
idx = 0
for color in range(3):
for _ in range(count[color]):
nums[idx] = color
idx += 1
Java
class Solution {
public void sortColors(int[] nums) {
int[] count = new int[3];
for (int i = 0; i < nums.length; i++) {
count[nums[i]]++;
}
int idx = 0;
for (int color = 0; color < 3; color++) {
for (int j = 0; j < count[color]; j++) {
nums[idx] = color;
idx++;
}
}
}
}
JavaScript
var sortColors = function (nums) {
let count = { 0: 0, 1: 0, 2: 0 };
for (let i = 0; i < nums.length; i++) {
count[nums[i]]++;
}
let idx = 0;
for (let color = 0; color < 3; color++) {
let freq = count[color];
for (let j = 0; j < freq; j++) {
nums[idx] = color;
idx++;
}
}
};