This approach involves counting the occurrences of each color and then overwriting the array with the correct number of zeros, ones, and twos. This is straightforward and efficiently utilizes fixed positions for each of the colors.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as it uses a fixed-size array.
1function sortColors(nums) {
2 const count = [0, 0, 0];
3 for (let num of nums) {
4 count[num]++;
5 }
6 let index = 0;
7 for (let i = 0; i < count[0]; i++) nums[index++] = 0;
8 for (let i = 0; i < count[1]; i++) nums[index++] = 1;
9 for (let i = 0; i < count[2]; i++) nums[index++] = 2;
10}
11
12// Example usage
13const nums = [2, 0, 2, 1, 1, 0];
14sortColors(nums);
15console.log(nums);In the JavaScript version, we declare an array to count occurrences of each color, then iterate through the initial nums array to record the count. Next, we overwrite the array with sorted colors based on these recorded counts.
This approach, modeled after the Dutch National Flag Problem, uses three pointers to partition the array into sections for 0s, 1s, and 2s. It performs a one-pass in-place sort by maintaining these fixed sections dynamically as it traverses the array.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed pointers.
1#include <stdio.h>
2
3void sortColors(int* nums, int numsSize) {
4 int low = 0, mid = 0, high = numsSize - 1;
5 while (mid <= high) {
6 if (nums[mid] == 0) {
7 int temp = nums[low];
8 nums[low] = nums[mid];
9 nums[mid] = temp;
10 low++; mid++;
11 } else if (nums[mid] == 1) {
12 mid++;
13 } else {
14 int temp = nums[mid];
15 nums[mid] = nums[high];
16 nums[high] = temp;
17 high--;
18 }
19 }
20}
21
22int main() {
23 int nums[] = {2,0,2,1,1,0};
24 int size = sizeof(nums) / sizeof(nums[0]);
25 sortColors(nums, size);
26 for (int i = 0; i < size; i++)
27 printf("%d ", nums[i]);
28 return 0;
29}In this C implementation, three pointers are maintained: low, mid, and high. The pointer low denotes the boundary for zeros, mid processes each element, and high indicates the start of twos. As the algorithm proceeds, swaps are made to ensure elements in positions up to low are 0s, up to mid are 1s, and post-high are 2s.