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 and Explanation

This problem can be efficiently solved using a three-pointer approach. We'll maintain three pointers:

1. p0: Points to the index where the next 0 (red) should be placed.
2. p1: Points to the index of the current element being considered.
3. p2: Points to the index where the next 2 (blue) should be placed.

Initially, p0 and p1 are at index 0, and p2 is at the last index. We iterate through the array using p1.

• If nums[p1] == 0, we swap nums[p1] and nums[p0], then increment both p0 and p1. This places the 0 in its correct position.
• If nums[p1] == 1, we only increment p1. The 1 is already in its potential sorted position.
• If nums[p1] == 2, we swap nums[p1] and nums[p2], then decrement p2. This moves the 2 to its correct position.

We continue this process until p1 crosses p2. This ensures that all elements are sorted in place.

Code (Java)

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, p1 = 0, p2 = nums.length - 1;
        
        while (p1 <= p2) {
            if (nums[p1] == 0) {
                swap(nums, p0, p1);
                p0++;
                p1++;
            } else if (nums[p1] == 1) {
                p1++;
            } else { // nums[p1] == 2
                swap(nums, p1, p2);
                p2--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Complexity Analysis

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

This three-pointer approach provides an optimal solution for the Sort Colors problem, achieving linear time complexity without requiring extra space.