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.
1#include <stdio.h>
2
3void sortColors(int* nums, int numsSize) {
4 int count[3] = {0};
5 for (int i = 0; i < numsSize; i++) {
6 count[nums[i]]++;
7 }
8 int index = 0;
9 for (int i = 0; i < count[0]; i++)
10 nums[index++] = 0;
11 for (int i = 0; i < count[1]; i++)
12 nums[index++] = 1;
13 for (int i = 0; i < count[2]; i++)
14 nums[index++] = 2;
15}
16
17int main() {
18 int nums[] = {2,0,2,1,1,0};
19 int size = sizeof(nums) / sizeof(nums[0]);
20 sortColors(nums, size);
21 for (int i = 0; i < size; i++)
22 printf("%d ", nums[i]);
23 return 0;
24}The function sortColors initializes a count array with three elements set to zero. It first iterates through the given array to count the number of 0s, 1s, and 2s. Then, it rewrites the original array based on these counts, placing the correct number of 0s, 1s, and 2s in order.
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.
1function sortColors(nums) {
2 let low = 0, mid = 0, high = nums.length - 1;
3 while (mid <= high) {
4 if (nums[mid] === 0) {
5 [nums[low], nums[mid]] = [nums[mid], nums[low]];
6 low++;
7 mid++;
8 } else if (nums[mid] === 1) {
9 mid++;
10 } else {
11 [nums[mid], nums[high]] = [nums[high], nums[mid]];
12 high--;
13 }
14 }
15}
16
17// Example usage
18const nums = [2, 0, 2, 1, 1, 0];
19sortColors(nums);
20console.log(nums);The JavaScript approach uses destructuring assignment to swap elements in place. The three-pointer technique ensures lowest indices contain zeros, middle ones contain ones, and highest indices contain twos.