Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Sort Colors solution and explanation

MediumArraySortingTwo Pointers5 min read69.9% acceptanceUpdated 9 Apr 2026
Asked atPocket GemsTargetSliceNagarroTCSWalmart Labs
+14 moreAgodaAutodeskMakeMyTripWorkdayAmazonMicrosoftMetaBloombergTiktokInfosyseBaySamsungMorgan StanleySwiggy
Practise Sort Colors
15:48
Sort Colors - Quicksort Partition - Leetcode 75 - PythonNeetCode · 15:48 · 149K viewsWatch on YouTube
9 more videos on this problem
  1. Sort Colors - Quicksort Partition - Leetcode 75 - PythonNeetCode · 15:48 · 149K views
  2. Sort colors | Leetcode #75Techdose · 6:02 · 91K views
  3. Sort Colors (LeetCode 75) | Dutch National Flag Problem | Full Solution with Visuals and AnimationsNikhil Lohia · 15:47 · 62K views
  4. LeetCode Sort Colors Solution Explained - JavaNick White · 7:40 · 34K views
  5. Sort Colors | Easy Explanation | Amazon | codestorywithMIKcodestorywithMIK · 14:08 · 24K views
  6. Sort Colors - Leetcode 75 - Arrays & Strings (Python)Greg Hogg · 7:18 · 10K views
  7. Sort Colors - LeetCode 75 - Coding Interview QuestionsOne Code Man · 4:20 · 2K views
  8. Sort Colors - LeetCode 75 - Python - Visually ExplainedHello Byte · 3:52 · 1K views
  9. #leetcode #tkggames #sortcolors LeetCode 75 : Sort Colors Solution|| javaTKGgames · 15:11 · 1K views
  10. Sort Colors - Leetcode 75 - JS (Javascript)Code With Ghanashri · 8:05 · 586 views

The problem

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?

Approach overview

Problem Overview: You receive an array containing only 0, 1, and 2, representing colors. The goal is to sort the array in-place so that elements appear in the order 0 → 1 → 2. The constraint is that you cannot use the built-in sort and should ideally solve it in a single pass with constant extra space.

Approach 1: Counting Sort (Two Pass) (Time: O(n), Space: O(1))

This approach counts how many times each value (0, 1, and 2) appears. First iterate through the array and maintain three counters: count0, count1, and count2. After collecting counts, iterate through the array again and overwrite values based on these frequencies. Fill the first count0 indices with 0, the next count1 indices with 1, and the remaining with 2. The algorithm runs in linear time because each element is processed twice at most. Extra space remains constant since only three counters are used. This method works well when the range of values is very small, but it requires two passes over the array. It mainly demonstrates a straightforward application of sorting principles.

Approach 2: Dutch National Flag Algorithm (One Pass) (Time: O(n), Space: O(1))

This is the optimal and most commonly expected interview solution. Maintain three pointers: low, mid, and high. The region before low contains sorted 0s, the region after high contains sorted 2s, and mid scans the array. When nums[mid] == 0, swap with nums[low] and move both pointers forward. When the value is 1, simply advance mid. When the value is 2, swap with nums[high] and decrement high without advancing mid. This partitioning process ensures every element is handled once, producing a single-pass in-place solution. The logic mirrors the classic Dutch National Flag partition used in quicksort-style partitioning and heavily relies on two pointers and careful boundary management within an array.

Recommended for interviews: The Dutch National Flag algorithm is what most interviewers expect. It demonstrates in-place partitioning, pointer control, and algorithmic optimization from two passes to one. Showing the counting approach first proves you understand the structure of the problem, but implementing the one-pass pointer strategy signals stronger problem-solving ability and familiarity with classic partitioning techniques.

Approach 1: Counting Sort Approach

This approach involves counting the occurrences of each color and then overwriting the array with the correct number of zeros, ones, and twos. This is straightforward and efficiently utilizes fixed positions for each of the colors.

def sortColors(nums):
    count = [0] * 3
    for num in nums:
        count[num] += 1
    index = 0
    for i in range(count[0]):
        nums[index] = 0
        index += 1
    for i in range(count[1]):
        nums[index] = 1
        index += 1
    for i in range(count[2]):
        nums[index] = 2
        index += 1

# Example usage
nums = [2,0,2,1,1,0]
sortColors(nums)
print(nums)
class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int num : nums) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i < count[0]; i++) nums[index++] = 0;
        for (int i = 0; i < count[1]; i++) nums[index++] = 1;
        for (int i = 0; i < count[2]; i++) nums[index++] = 2;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        sol.sortColors(nums);
        for (int num : nums) System.out.print(num + " ");
    }
}
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int count[3] = {0};
    for (int num : nums) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count[0]; ++i)
        nums[index++] = 0;
    for (int i = 0; i < count[1]; ++i)
        nums[index++] = 1;
    for (int i = 0; i < count[2]; ++i)
        nums[index++] = 2;
}

int main() {
    vector<int> nums = {2,0,2,1,1,0};
    sortColors(nums);
    for (int i : nums)
        cout << i << " ";
    return 0;
}
function sortColors(nums) {
    const count = [0, 0, 0];
    for (let num of nums) {
        count[num]++;
    }
    let index = 0;
    for (let i = 0; i < count[0]; i++) nums[index++] = 0;
    for (let i = 0; i < count[1]; i++) nums[index++] = 1;
    for (let i = 0; i < count[2]; i++) nums[index++] = 2;
}

// Example usage
const nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);
console.log(nums);
#include <stdio.h>

void sortColors(int* nums, int numsSize) {
    int count[3] = {0};
    for (int i = 0; i < numsSize; i++) {
        count[nums[i]]++;
    }
    int index = 0;
    for (int i = 0; i < count[0]; i++)
        nums[index++] = 0;
    for (int i = 0; i < count[1]; i++)
        nums[index++] = 1;
    for (int i = 0; i < count[2]; i++)
        nums[index++] = 2;
}

int main() {
    int nums[] = {2,0,2,1,1,0};
    int size = sizeof(nums) / sizeof(nums[0]);
    sortColors(nums, size);
    for (int i = 0; i < size; i++)
        printf("%d ", nums[i]);
    return 0;
}
using System;

public class Solution {
    public void SortColors(int[] nums) {
        int[] count = new int[3];
        foreach (int num in nums) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i < count[0]; i++) nums[index++] = 0;
        for (int i = 0; i < count[1]; i++) nums[index++] = 1;
        for (int i = 0; i < count[2]; i++) nums[index++] = 2;
    }

    public static void Main() {
        Solution solution = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        solution.SortColors(nums);
        Console.WriteLine(String.Join(" ", nums));
    }
}

In the Python solution, a list named count is used to store the count of each color. It iterates through the nums list to populate this count, then overwrites the list with the appropriate quantities of each color in order.

Complexity

Time Complexity: O(n), where n represents the length of the list.
Space Complexity: O(1), since it utilizes a temporary list of fixed size.

Try this approach in the editor

Approach 2: Dutch National Flag Problem Solution

This approach, modeled after the Dutch National Flag Problem, uses three pointers to partition the array into sections for 0s, 1s, and 2s. It performs a one-pass in-place sort by maintaining these fixed sections dynamically as it traverses the array.

def sortColors(nums):
    low, mid, high = 0, 0, 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], nums[high] = nums[high], nums[mid]
            high -= 1

# Example usage
nums = [2,0,2,1,1,0]
sortColors(nums)
print(nums)
class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    int temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++; mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    break;
            }
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        sol.sortColors(nums);
        for (int num : nums)
            System.out.print(num + " ");
    }
}
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        switch (nums[mid]) {
            case 0:
                swap(nums[low++], nums[mid++]);
                break;
            case 1:
                mid++;
                break;
            case 2:
                swap(nums[mid], nums[high--]);
                break;
        }
    }
}

int main() {
    vector<int> nums = {2,0,2,1,1,0};
    sortColors(nums);
    for (int num : nums)
        cout << num << " ";
    return 0;
}
function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

// Example usage
const nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);
console.log(nums);
#include <stdio.h>

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            low++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            high--;
        }
    }
}

int main() {
    int nums[] = {2,0,2,1,1,0};
    int size = sizeof(nums) / sizeof(nums[0]);
    sortColors(nums, size);
    for (int i = 0; i < size; i++)
        printf("%d ", nums[i]);
    return 0;
}
using System;

public class Solution {
    public void SortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.Length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low++] = nums[mid];
                nums[mid++] = temp;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high--] = temp;
            }
        }
    }

    public static void Main() {
        Solution solution = new Solution();
        int[] nums = {2, 0, 2, 1, 1, 0};
        solution.SortColors(nums);
        Console.WriteLine(String.Join(" ", nums));
    }
}

Here, the Python function uses the concept of three pointers. It processes each element, moving 0s to the low section, 1s to mid, and 2s toward high, swapping as needed.

Complexity

Time Complexity: O(n), consistent with the input size.
Space Complexity: O(1), benefiting from the in-place swapping mechanism.

Try this approach in the editor

Approach 3: Three Pointers

We define three pointers i, j, and k. Pointer i is used to point to the rightmost boundary of the elements with a value of 0 in the array, and pointer j is used to point to the leftmost boundary of the elements with a value of 2 in the array. Initially, i=-1, j=n. Pointer k is used to point to the current element being traversed, initially k=0.

When k < j, we perform the following operations:

  • If nums[k] = 0, then swap it with nums[i+1], then increment both i and k by 1;
  • If nums[k] = 2, then swap it with nums[j-1], then decrement j by 1;
  • If nums[k] = 1, then increment k by 1.

After the traversal, the elements in the array are divided into three parts: [0,i], [i+1,j-1] and [j,n-1].

The time complexity is O(n), where n is the length of the array. Only one traversal of the array is needed. The space complexity is O(1).

/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
    let i = -1;
    let j = nums.length;
    let k = 0;
    while (k < j) {
        if (nums[k] === 0) {
            ++i;
            [nums[i], nums[k]] = [nums[k], nums[i]];
            ++k;
        } else if (nums[k] === 2) {
            --j;
            [nums[j], nums[k]] = [nums[k], nums[j]];
        } else {
            ++k;
        }
    }
}
func sortColors(nums []int) {
	i, j, k := -1, len(nums), 0
	for k < j {
		if nums[k] == 0 {
			i++
			nums[i], nums[k] = nums[k], nums[i]
			k++
		} else if nums[k] == 2 {
			j--
			nums[j], nums[k] = nums[k], nums[j]
		} else {
			k++
		}
	}
}
impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let mut i = -1;
        let mut j = nums.len();
        let mut k = 0;
        while k < j {
            if nums[k] == 0 {
                i += 1;
                nums.swap(i as usize, k as usize);
                k += 1;
            } else if nums[k] == 2 {
                j -= 1;
                nums.swap(j, k);
            } else {
                k += 1;
            }
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Counting Sort Approach

Time Complexity: O(n), where n represents the length of the list.
Space Complexity: O(1), since it utilizes a temporary list of fixed size.

Dutch National Flag Problem Solution

Time Complexity: O(n), consistent with the input size.
Space Complexity: O(1), benefiting from the in-place swapping mechanism.

Three Pointers–

Complexity analysis

ApproachTimeSpaceWhen to Use
Counting Sort (Two Pass)O(n)O(1)Simple implementation when value range is fixed and multiple passes are acceptable
Dutch National Flag AlgorithmO(n)O(1)Best for interviews; single-pass in-place partitioning

Frequently asked questions

Is Sort Colors easy or hard?

Sort Colors is considered a medium-level problem. The brute-force counting approach is straightforward, but recognizing and implementing the Dutch National Flag algorithm requires stronger understanding of pointer-based partitioning.

Sort Colors Python/Java solution

Python and Java implementations typically follow the Dutch National Flag pattern. Both versions maintain three indices and perform conditional swaps while scanning the array once, achieving O(n) time and O(1) space complexity.

How to solve Sort Colors in O(n)?

Use the Dutch National Flag technique with three pointers. Maintain regions for 0s, 1s, and 2s while iterating with a mid pointer. Swap elements into their correct regions as you scan the array, which guarantees a single linear pass and constant space.

What is the best approach for Sort Colors?

The Dutch National Flag algorithm is the best approach. It uses three pointers (low, mid, high) to partition the array in a single pass. This method runs in O(n) time and O(1) space while sorting the array in-place without using a built-in sort.

Is Sort Colors asked at Google/Amazon/Meta?

Sort Colors frequently appears in interviews at companies like Amazon, Meta, and Google because it tests array manipulation, in-place partitioning, and pointer logic. Variations of the Dutch National Flag problem are also common in system-level coding rounds.

What data structure is used in Sort Colors?

The problem primarily uses an array with pointer manipulation. The optimal solution relies on the two-pointer technique extended to three boundaries for in-place partitioning of values.

What is the time complexity of Sort Colors?

The optimal solution runs in O(n) time because each element is processed at most once. The Dutch National Flag algorithm performs constant-time swaps and pointer updates while scanning the array exactly once.

Comments

Next problem · similarSort ListMedium
Now write it yourselfClose this page and solve Sort Colors in the editor, without looking.
Practise Sort Colors