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 without using sorting functions is to use a three-pointer approach. We'll use three pointers:

• p0: Points to the index where the next 0 should be placed.
• p1: Points to the index of the currently processed element.
• p2: Points to the index where the next 2 should be placed.

We iterate through the array using p1. Based on the value of nums[p1]:

1. If nums[p1] == 0: Swap nums[p0] and nums[p1], then increment both p0 and p1.
2. If nums[p1] == 1: Increment p1 only.
3. If nums[p1] == 2: Swap nums[p1] and nums[p2], then decrement p2. Note that we don't increment p1 in this case because the element at nums[p2] (which was swapped into nums[p1]) hasn't been processed yet.

This process ensures that all 0s are placed before all 1s, and all 1s are placed before all 2s, all within a single pass.

Explanation

The algorithm maintains three sections within the array:

• Section 0 (0 to p0-1): Filled with 0s.
• Section 1 (p0 to p1-1): Filled with 1s (or unprocessed elements).
• Section 2 (p2 to n-1): Filled with 2s.

The algorithm iteratively expands section 0 and section 2 while shrinking section 1. The key is that swaps only occur between elements outside of section 1, ensuring that the relative order of elements within each section is not disrupted.

Code

def sortColors(nums):
    """
    Sorts an array of 0s, 1s, and 2s in-place using a three-pointer approach.

    Args:
      nums: A list of integers representing the colors (0, 1, 2).
    """
    p0 = 0  # Pointer for 0s
    p1 = 0  # Pointer for current element
    p2 = len(nums) - 1  # Pointer for 2s

    while p1 <= p2:
        if nums[p1] == 0:
            nums[p0], nums[p1] = nums[p1], nums[p0]
            p0 += 1
            p1 += 1
        elif nums[p1] == 1:
            p1 += 1
        else:  # nums[p1] == 2
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p2 -= 1

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. This is an in-place sorting algorithm.