Sort Colors medium

Problem Statement

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]

Steps

The key to solving this problem efficiently and in-place is using a three-pointer approach. We'll maintain three pointers:

1. p0: Points to the beginning of the 0s (red) region.
2. i: The current index being processed.
3. p2: Points to the end of the 2s (blue) region.

We iterate through the array using i. The logic is as follows:

• If nums[i] == 0, we swap nums[i] and nums[p0], and increment both i and p0.
• If nums[i] == 1, we only increment i.
• If nums[i] == 2, we swap nums[i] and nums[p2], and decrement p2.

This ensures that 0s are placed at the beginning, 1s in the middle, and 2s at the end.

Explanation

The algorithm works because it maintains three distinct regions:

• [0, p0): Contains only 0s (red).
• [p0, i): Contains a mix of 0s, 1s, and potentially unprocessed elements.
• [i, p2): Contains a mix of 1s, 2s, and potentially unprocessed elements.
• [p2, n): Contains only 2s (blue).

The algorithm systematically moves elements from the mixed regions into their correct positions, expanding the regions of 0s and 2s. The key is that swapping a 0 with nums[p0] always results in a valid arrangement, and swapping a 2 with nums[p2] does the same.

Code

#include <iostream>
#include <vector>

void sortColors(std::vector<int>& nums) {
    int p0 = 0, i = 0, p2 = nums.size() - 1;
    while (i <= p2) {
        if (nums[i] == 0) {
            std::swap(nums[i++], nums[p0++]);
        } else if (nums[i] == 1) {
            i++;
        } else {
            std::swap(nums[i], nums[p2--]);
        }
    }
}


int main() {
    std::vector<int> nums1 = {2, 0, 2, 1, 1, 0};
    sortColors(nums1);
    for (int num : nums1) {
        std::cout << num << " ";
    }
    std::cout << std::endl; //Output: 0 0 1 1 2 2

    std::vector<int> nums2 = {2, 0, 1};
    sortColors(nums2);
    for (int num : nums2) {
        std::cout << num << " ";
    }
    std::cout << std::endl; //Output: 0 1 2

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the array. We iterate through the array at most once.
• Space Complexity: O(1). We use only a constant amount of extra space for the pointers.