LeetCode 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.

Solution (two pointers):

The goal is to sort an array of 0s, 1s, and 2s in-place so that all 0s come first, then all 1s, then all 2s — without using any built-in sort functions or extra space.

We maintain three regions in the array:

• [0, start-1] → all 0s
• [start, current-1] → all 1s
• [current, end] → unknown/unprocessed
• [end+1, n-1] → all 2s

We use three pointers:

• start — boundary for the region of 0s.
• current — current index being examined.
• end — boundary for the region of 2s.

void sortColors(vector<int>& nums) {
    int start = 0;                // pointer for placing 0s
    int current = 0;              // pointer for current element
    int end = nums.size() - 1;    // pointer for placing 2s

    // Process elements until current crosses end
    while (current <= end) {
        if (nums[current] == 0) {
            // Swap current 0 to the start region
            std::swap(nums[current], nums[start]);
            start++;
            current++; // Move both pointers forward
        }
        else if (nums[current] == 1) {
            // 1 is in the right region already
            current++;
        }
        else { // nums[current] == 2
            // Swap current 2 to the end region
            std::swap(nums[current], nums[end]);
            end--;
            // Do NOT increment current — the swapped-in value must be processed next
        }
    }
}

Overall time complexity: O(n)