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 most efficient approach to solve this problem is using a three-pointer technique. We'll use three pointers:

1. p0: Points to the index where the next 0 should be placed.
2. p1: Iterates through the array.
3. p2: Points to the index where the next 2 should be placed.

We iterate through the array using p1. If we find a 0, we swap it with the element at p0 and increment p0. If we find a 2, we swap it with the element at p2 and decrement p2. If we find a 1, we simply continue. This ensures that 0s are placed at the beginning, 2s are placed at the end, and 1s are left in the middle.

Explanation

The algorithm cleverly uses the fact that we only have three colors. By maintaining the p0 and p2 pointers, we create partitions in the array:

• Elements from index 0 to p0 - 1 are 0s.
• Elements from index p0 to p1 - 1 are 1s (or unsorted elements).
• Elements from index p1 to p2 are unsorted elements.
• Elements from index p2 + 1 to n - 1 are 2s.

As p1 iterates, it maintains and adjusts these partitions. The key is that swapping a 0 to the p0 position doesn't affect the 2s already placed at the end (and vice versa). This avoids unnecessary swaps and ensures in-place sorting.

Code

public class Solution {
    public void SortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        int p2 = nums.Length - 1;

        while (p1 <= p2) {
            if (nums[p1] == 0) {
                Swap(nums, p0, p1);
                p0++;
                p1++;
            } else if (nums[p1] == 2) {
                Swap(nums, p1, p2);
                p2--;
            } else {
                p1++;
            }
        }
    }

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

Complexity

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