Problem 23 - Sort Colors

Explore our archive for previous posts.

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.

Approach

The problem requires sorting an array containing elements representing three colors: red (0), white (1), and blue (2). The goal is to arrange the colors in-place such that all the red elements come before the white elements, and all the white elements come before the blue elements.

One could very easily just sort the entire array which would get all 0’s in the front followed by 1’s and then the 2’s. However, the problem statement clearly states that we shouldn’t use the sort functionality to solve the problem.

The solution uses the Dutch National Flag algorithm, which employs three pointers to partition the array into three sections representing the three colors: red (0), white (1), and blue (2). The red pointer keeps track of the next position to place a 0, the white pointer traverses the array, and the blue pointer keeps track of the next position to place a 2. The algorithm iterates through the array and performs swaps based on the color encountered at the white pointer, effectively sorting the colors in place.

At the end of all iterations, the final positions of the 'red', 'white', and 'blue' pointers will be as follows:

1. The 'red' pointer will be pointing to the index just after the last red (0) element. All elements before this position will be 0.

2. The 'white' pointer will be pointing to the index just after the last white (1) element. All elements between the 'red' pointer and the 'white' pointer will be 1.

3. The 'blue' pointer will be pointing to the index just before the first blue (2) element. All elements after this position will be 2.

Solution

Solve it here

class Solution {
    public void sortColors(int[] nums) {
        int red = 0; // Pointer for 0 (red) color
        int white = 0; // Pointer for 1 (white) color
        int blue = nums.length - 1; // Pointer for 2 (blue) color
        
        while (white <= blue) {
            if (nums[white] == 0) {
                swap(nums, red, white); // Swap red and white elements
                red++; // Move red pointer forward
                white++; // Move white pointer forward
            } else if (nums[white] == 1) {
                white++; // Move white pointer forward
            } else {
                swap(nums, white, blue); // Swap white and blue elements
                blue--; // Move blue pointer backward
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Time and space complexity

Time Complexity: The solution traverses the array once, so the time complexity is O(n), where 'n' is the length of the input array.

Space Complexity: The solution operates in-place, modifying the input array without using additional data structures. Hence, the space complexity is O(1), as the space usage remains constant regardless of the array size.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!