LeetCode //C - 75. Sort Colors

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.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

From: LeetCode
Link: 75. Sort Colors

---

Solution:

Ideas:

1. Initialization: Three pointers are used, low, mid, and high, which initially point to the beginning of the array, the beginning of the array, and the end of the array, respectively.

• The low pointer is intended to track the boundary of the zeros (reds). Everything before low should be 0 after sorting.
• The mid pointer traverses the array from start to end. It represents the current element being considered and helps examine each element in the array.
• The high pointer is intended to track the boundary of the twos (blues). Everything after high should be 2 after sorting.

2. Iterative Processing: The mid pointer is used to iterate over the array. For each element at mid:

• If the element is 0 (red), it should be at the beginning of the array. So, it’s swapped with the element at low, and both low and mid are incremented. Incrementing mid as well is safe because the element swapped to mid was previously at low, which means it must have been already examined (and thus must be 1, since all 0s are moved to the left of low).
• If the element is 1 (white), it’s already in the correct section of the array, so mid is simply incremented.
• If the element is 2 (blue), it should be at the end of the array. So, it’s swapped with the element at high, and high is decremented. Mid is not incremented in this case because the swapped-in element has not been examined yet.

3. Termination: The process continues until mid exceeds high. At this point, all 0s are to the left of low, all 2s are to the right of high, and 1s are naturally between low and high.

Code:

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;
    
    while (mid <= high) {
        switch (nums[mid]) {
            case 0: // Red
                swap(&nums[low++], &nums[mid++]);
                break;
            case 1: // White
                mid++;
                break;
            case 2: // Blue
                swap(&nums[mid], &nums[high--]);
                break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23