LeetCode Solutions Blog

Sort Colors

Number: 75

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers where each integer represents a color (0 for red, 1 for white, and 2 for blue), sort the array in a single pass and in-place so that objects of the same color are adjacent and arranged in the order red, white, blue.

Key Insights

Use the Dutch National Flag algorithm to partition the array into three sections.
Maintain three pointers: one for the next position for 0 (low), one for the next position for 2 (high), and one to traverse the array (mid).
Swap elements appropriately to ensure that all 0's are at the beginning, all 2's are at the end, and 1's remain in the middle.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

The solution uses a three-pointer approach (Dutch National Flag algorithm). Initialize three pointers: low, mid, and high. As you iterate through the array:

If the element is 0, swap it with the element at the low pointer and increment both low and mid.
If the element is 1, simply move mid forward.
If the element is 2, swap it with the element at the high pointer and decrement high. This single pass method ensures that the array is sorted in-place with constant extra space. Key details include correctly handling swaps without losing any data and ensuring that the pointers are updated in the proper order.

Code Solutions

# Function to sort the colors using Dutch National Flag algorithm
def sortColors(nums):
    # Initialize pointers for the start, current, and end positions
    low, mid, high = 0, 0, len(nums) - 1

    # Process elements until mid pointer exceeds high pointer
    while mid <= high:
        # If the current element is 0 (red)
        if nums[mid] == 0:
            # Swap current element with the element at low pointer
            nums[low], nums[mid] = nums[mid], nums[low]
            # Increment both low and mid pointers
            low += 1
            mid += 1
        # If the current element is 1 (white)
        elif nums[mid] == 1:
            # Move mid pointer forward since it's already in the correct place
            mid += 1
        # If the current element is 2 (blue)
        else:
            # Swap current element with the element at high pointer
            nums[mid], nums[high] = nums[high], nums[mid]
            # Decrement high pointer
            high -= 1

# Example usage:
nums = [2,0,2,1,1,0]
sortColors(nums)
print(nums)  # Output: [0,0,1,1,2,2]