Sort Colors

🔴 Problem Statement:

Given an array nums with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, blue (i.e., 0s, then 1s, then 2s).

• You must solve this problem without using the library's sort function.

✅ Example:

Input:  nums = [2,0,2,1,1,0]
Output:        [0,0,1,1,2,2]

🔍 Algorithm (Dutch National Flag Algorithm):

We use three pointers:

low → to place 0s

mid → current index

high → to place 2s

Steps:

Initialize:

low = 0

mid = 0

high = n - 1

Traverse while mid <= high:

If nums[mid] == 0:

Swap nums[low] and nums[mid]

Increment low and mid

Else if nums[mid] == 1:

Just move mid forward

Else if nums[mid] == 2:

Swap nums[mid] and nums[high]

Decrement high (don’t move mid yet)

Why not increment mid when swapping with high?

Because the swapped value from the high index could be 0 or 2, and we need to check it again.

code Cpp

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else { // nums[mid] == 2
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

int main() {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);

    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

Java Code

import java.util.Arrays;

public class SortColors {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }
}

🧠 Time & Space Complexity

Time Complexity: O(n) → Each element is visited at most once.

Space Complexity: O(1) → No extra space used, sorting done in-place.

Python code

def sortColors(nums):
    low = 0
    mid = 0
    high = len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

# Example usage:
nums = [2, 0, 2, 1, 1, 0]
sortColors(nums)
print(nums)  # Output: [0, 0, 1, 1, 2, 2]

some common interview questions and answers related to the Sort Colors

🔶 1. What is the main idea behind the Dutch National Flag algorithm?

Answer:
The idea is to sort an array with only three distinct values (0, 1, 2) in a single traversal using     three pointers:

low for 0s,

mid for traversal,

high for 2s.

We keep placing elements in the correct position by swapping, depending on their values.

🔶 2. Why is this algorithm more efficient than using a sorting function?

Answer:
This algorithm sorts in O(n) time and O(1) space, whereas comparison-based sorting algorithms take at least O(n log n) time. It’s more efficient and tailored specifically for three distinct values.

🔶 3. Can this problem be solved using counting sort? How?

Answer:
Yes.

First pass: Count the number of 0s, 1s, and 2s.

Second pass: Overwrite the array using the counts.

But this uses two passes, while the Dutch National Flag algorithm solves it in one pass.

🔶 4. Is the algorithm stable?

Answer:
No.

This algorithm swaps elements, and therefore does not maintain the original relative order of equal     elements.

🔶 5. Can this approach be generalized to sort more than 3 unique elements?

Answer:
No,
the Dutch National Flag algorithm is specifically designed for three unique values.
For more values, you'd need a general-purpose algorithm like counting sort or bucket sort.

🔶 6. Why do we decrement high but not increment mid after swapping with high?

Answer:
Because after swapping with high, the new value at mid might be:

0: Needs to be swapped with low.

1: Okay.

2: Needs to be swapped again.

So we re-check mid instead of skipping it.

🔶 7. What is the time and space complexity of this algorithm?

Answer:

Time Complexity: O(n) – each element is visited at most once.

Space Complexity: O(1) – sorting is done in-place.