We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort Colors

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be solved using a three-way partitioning algorithm, which is efficient for sorting arrays with a limited range of values (in this case, 0, 1, and 2).
  • We can use two pointers to track the boundaries of the current segment of colors being processed.
  • The algorithm can be executed in a single pass through the array, achieving O(n) time complexity.
  • The solution requires constant space, as it modifies the input array in place.

Space and Time Complexity

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

Solution

The solution employs a three-pointer technique: one pointer for the current element, one for the position of the next 0 (red), and another for the position of the next 2 (blue). We iterate through the array, and based on the value at the current pointer, we swap elements to their correct positions as follows:

  1. If the current element is 0, swap it with the next position of 0 and move both pointers forward.
  2. If the current element is 1, just move the current pointer forward.
  3. If the current element is 2, swap it with the next position of 2 and move the pointer for 2 backward, but do not move the current pointer forward until we check the swapped value.

This approach ensures that all elements are sorted in a single pass.

Code Solutions

def sortColors(nums):
    zero_index = 0  # Pointer for the next position of 0
    two_index = len(nums) - 1  # Pointer for the next position of 2
    current = 0  # Current pointer
    
    while current <= two_index:
        if nums[current] == 0:
            nums[current], nums[zero_index] = nums[zero_index], nums[current]
            zero_index += 1
            current += 1
        elif nums[current] == 1:
            current += 1
        else:  # nums[current] == 2
            nums[current], nums[two_index] = nums[two_index], nums[current]
            two_index -= 1

# Example usage:
# nums = [2,0,2,1,1,0]
# sortColors(nums)
# Output: [0,0,1,1,2,2]
← Back to All Questions