Skip to main content
Talentd

Sort Colors - Solution & Explanation

MediumArrayTwo PointersSorting20 min readAsked at: Amazon, Microsoft, Apple +34
Practice this problem

Problem Statement

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.

The function sortColors initializes a count array with three elements set to zero. It first iterates through the given array to count the number of 0s, 1s, and 2s. Then, it rewrites the original array based on these counts, placing the correct number of 0s, 1s, and 2s in order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as it uses a fixed-size array.

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.

In this C implementation, three pointers are maintained: low, mid, and high. The pointer low denotes the boundary for zeros, mid processes each element, and high indicates the start of twos. As the algorithm proceeds, swaps are made to ensure elements in positions up to low are 0s, up to mid are 1s, and post-high are 2s.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed pointers.

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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Sort Approach

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as it uses a fixed-size array.

Dutch National Flag Problem Solution

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed pointers.

Three Pointers—

Detailed 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

Video Solution

Sort Colors - Quicksort Partition - Leetcode 75 - Python • NeetCode • 149,073 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sort Colors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort List

Next

Wiggle Sort