Solution: Sort Colors

Statement

Given an array, colors, which contains a combination of the following three elements:

• $0$ (representing red)

• $1$ (representing white)

• $2$ (representing blue)

Sort the array in place so that the elements of the same color are adjacent, with the colors in the order of red, white, and blue. To improve your problem-solving skills, do not utilize the built-in sort function.

Constraints:

• $1 \leq$ colors.length $\leq$ 300
• colors[i] can only contain $0$s, $1$s, or $2$s.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be to sort the array. This would arrange the elements in the desired positions, i.e., $0$s, then $1$s, and lastly, $2$s. The time complexity of this approach would be $O(n \log(n))$, which is the time required to sort the array. The space complexity of this approach would be $O(1)$ since no extra space is being used.

Optimized approach using two pointers

The problem statement asks us to solve this problem in place and without using any built-in sort functionality. This can be achieved in a single pass by using an algorithm that partitions the colors array into three sections: red, white, and blue. As the arrangement resembles the Dutch national flag, the approach is commonly known as the Dutch National Flag algorithm.

The key idea is to maintain boundaries for the red and blue sections while iterating through the array. Reds are placed on the left side of the array, blues on the right, and whites in between. When encountering a red ($0$), we place it at the end of the red section, and when a blue ($2$) is found, we move it to the beginning of the blue section. The remaining white ($1$) elements will remain in place. We continue this process until all the colors are separated, ensuring proper grouping of colors.

To implement the Dutch National Flag algorithm, we’ll use two pointers; start and end. The start and end pointers will keep track of the boundaries of red and blue sections respectively. In addition, we maintain another pointer (current) to keep track of the white elements.

The pointers are initialized as follows:

• start and current: These pointers will initially point to the first index of the colors array.

• end: This pointer will initially point to the last index of the colors array.

Here’s how the algorithm works:

We start by iterating over the colors array until the current pointer exceeds the end pointer, i.e., current <= end. During this iteration, we perform the following three conditions:

• Condition 1: If colors[current] is 0:

  • The current pointer points to red. Swap the elements of colors[current] and colors[start]. This ensures the red element is placed at the beginning of the array.

  • Next, increment both the start and current pointers one position forward. Moving start ensures that the next red element will occupy the correct position.

• Condition 2: If colors[current] is 1:

  • The element (white) is already in its correct section (middle of the array), so no swapping is required.

  • Increment the current pointer by 1 to analyze the next element.

• Condition 3: If colors[current] is 2:

  • The current pointer points to blue. Swap the elements of colors[current] and colors[end]. This pushes the blue element to the end of the array.

  • Next, decrement the end pointer one position backward to reduce the section for blue elements.

Note: When we decrement the end pointer, the current pointer remains unchanged since it has to analyze the swapped element to determine if further swapping is required with the start pointer.

The three steps above are repeated until the end pointer becomes less than the current pointer, i.e., no elements are left to swap.

Let’s look at the following illustration to get a better understanding of the solution: