Dare2Solve
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.
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.
0
s, 1
s, and 2
s.0
s, followed by 1
s, and then 2
s based on the counts from the first phase.O(n) - where n
is the length of the array. We traverse the array twice: once for counting and once for overwriting.
O(1) - We only use a fixed amount of extra space for the count array, making this approach very space-efficient.
class Solution {
public:
void sortColors(vector<int>& 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++;
}
}
}
};
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
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++;
}
}
}
}
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++;
}
}
};