Sort Colors

LeetCode 75 | Difficulty: Medium

Medium

Problem Description

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?

Topics: Array, Two Pointers, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

---

Solutions

Solution 1: C# (Best: 108 ms)

Metric	Value
Runtime	108 ms
Memory	40.7 MB
Date	2021-12-28

Solution

public class Solution {
    public void SortColors(int[] nums) {
    int i=0, j=0, n=nums.Length-1;
    int mid=1;
    while(j<=n)
    {
        if(nums[j]<mid)
        {
            swap(nums,i,j);
            i++;
            j++;
        }
        else if(nums[j]>mid)
        {
            swap(nums, j, n);
            n--;
        }
        else j++;
    }
    
}

void swap(int[] nums, int l, int r)
{
    if(l==r) return;
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}
}

📜 2 more C# submission(s)

Submission (2018-04-12) — 284 ms, N/A

public class Solution {
    public void SortColors(int[] nums) {
int i=0, j=0, n=nums.Length-1;
    int mid=1;
    while(j<=n)
    {
        if(nums[j]<mid)
        {
            swap(nums,i,j);
            i++;
            j++;
        }
        else if(nums[j]>mid)
        {
            swap(nums, j, n);
            n--;
        }
        else j++;
    }
    
}

void swap(int[] nums, int l, int r)
{
    if(l==r) return;
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}
}

Submission (2018-04-12) — 292 ms, N/A

public class Solution {
    public void SortColors(int[] nums) {
int i=0, j=0, n=nums.Length-1;
    int mid=1;
    while(j<=n)
    {
        if(nums[j]<mid)
        {
            swap(nums,i,j);
            i++;
            j++;
        }
        else if(nums[j]>mid)
        {
            swap(nums, j, n);
            n--;
        }
        else j++;
    }
    
}

void swap(int[] nums, int l, int r)
{
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: A rather straight forward solution is a two-pass algorithm using counting sort.

Hint 2: Iterate the array counting number of 0's, 1's, and 2's.

Hint 3: Overwrite array with the total number of 0's, then 1's and followed by 2's.