Problem Description

Question

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]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solve it on LeetCode

Approaches

1. Counting Sort

Intuition:

The problem can be solved by first counting the number of occurrences of each color (0s, 1s, and 2s). This information can be used to overwrite the original array by placing the colors consecutively as per the number of occurrences. Although this is not done in one-pass, it is straightforward and efficient.

Steps:

Count the number of 0s, 1s, and 2s in the array.
Overwrite the array with the correct number of 0s, followed by 1s, and then 2s.

Code:

Complexity Analysis

Time Complexity: O(n), where n is the number of elements in the array. We iterate over the array twice (once to count and once to overwrite), so it's linear.
Space Complexity: O(1), since we are only using a fixed amount of extra space (three counters and an index).

2. One-pass Dutch National Flag Problem (Three Pointers)

Intuition:

This approach utilizes the famous Dutch National Flag algorithm which sorts the array using one pass and constant space by maintaining three pointers: low, mid, and high.

low maintains the boundary of zeros.
mid iterates over the array.
high maintains the boundary of twos.

Steps:

Initialize three pointers: low at the start, mid at the start, and high at the end of the array.
While mid is less than or equal to high:

If the element at mid is 0, swap it with the element at low. Increment both low and mid.
If the element at mid is 1, just increment mid.
If the element at mid is 2, swap it with the element at high. Decrement high (do not increment mid because the swapped element from high may need further processing).

Code:

Complexity Analysis

Time Complexity: O(n), where n is the number of elements in the array. We perform a single linear scan of the array.
Space Complexity: O(1), as we are using only constant extra space for the pointers.

Sort Colors

Ashish Pratap Singh

Problem Description

Example 1:

Example 2:

Constraints:

Solve it on LeetCode

Approaches

1. Counting Sort

Intuition:

Steps:

Code:

2. One-pass Dutch National Flag Problem (Three Pointers)

Intuition:

Steps:

Code:

Get Premium