[Two Pointers] Sort Colors

Sort Colors problem

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≤ colors.length ≤300
• colors[i] can only contain 0s, 1s, or 2s.

Approaches

1. Introduce three pointers that will act as boundaries for the three colors in the array

2. Iterate through the array to process each element based on its value.

3. If the current color corresponds to 0 (red), we swap the elements to move it to the red section at the start of the array. The current color is placed at the end of the red section, and we then move to the next element.

4. Else, if the current color corresponds to 1 (white), leave it in place and move to the next element.

5. Otherwise, the current color corresponds to 2 (blue), we swap the elements to move them to the blue section at the end of the array, and the current color is placed at the start of the blue section.

6. Continue the process above until all elements have been iterated.

 

def sort_colors(colors):
  length = len(colors)
  start, end = 0, length-1
  current = 0
  
  while current <= end:
    if colors[current] == 0:
      colors[current] = colors[start]
      current += 1
      start += 1
      
    elif colors[current] == 1:
      current += 1
    
    elif colors[current] == 2:
      colors[current] = colors[end]
      end -= 1
  
      
  # Replace this placeholder return statement with your code  
  return colors

 

Solution

1. Naive approach: Naive approach would be to sort the array. This would arrange the elements in the desired positions. The time complexity of this approach would be O(nlog(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.

2. Optimized approach using two pointers: The problem statement asks us to solve this problem in place and witout using any built-in sort functionality. This can be achieved in a single pass 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 maintaining boundaries for the red and blue sections while iterating through the array. Reds are placed on the left sife of the array, blues on the right, and white 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 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 will use two pointers: start and end, The start and end pointers will keep track of the boundaries of the red and blue sections, respectively. In addition, we maintain another pointer(current) to keep track of the white elements.

The pointers are initalized as follows: 

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

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

 

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

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.

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.

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 reduece the section for blue elements.

*When we decrement the end pointer, the current pointer remains unchanged since it has to analyze the swapped element to determine if futher 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. 

 

def sort_colors(colors):
    # Initialize the start, current, and end pointers
    start, current, end = 0, 0, len(colors) - 1

    # Iterate through the list until the current pointer exceeds the end pointer
    while current <= end:
        if colors[current] == 0:
            # If the current element is 0 (red), swap it with the element at the start pointer
            # This ensures the red element is placed at the beginning of the array
            colors[start], colors[current] = colors[current], colors[start]
            # Move both the start and current pointers one position forward
            current += 1
            start += 1

        elif colors[current] == 1:
            # If the current element is 1 (white), just move the current pointer one position forward
            current += 1

        else:
            # If the current element is 2 (blue), swap it with the element at the end pointer
            # This pushes the blue element to the end of the array
            colors[current], colors[end] = colors[end], colors[current]
            # Move the end pointer one position backward
            end -= 1
    return colors

 

1. Traverse the array and swap elements, as required, to organize them correctly.

2. If the encountered color is red, swap its value with that of the start pointer. If the color is blue, swap its value with that of the end pointer.

3. White elements are skipped, and pointers are adjusted accordingly.

4. The array is sorted when the end pointer moves to the left of the current pointer.

 

Time complexity: O(n)

Traversing the array once

 

Spae complexity: O(1)

O(1) since no extra space is used.