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.length1 <= n <= 300nums[i] is either 0, 1, or 2.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
Problem Overview: You’re given an array containing only 0, 1, and 2. The goal is to sort it in-place so that all 0s come first, followed by 1s, then 2s. The constraint that only three values exist opens the door to specialized techniques beyond general-purpose sorting.
Approach 1: Counting Sort (O(n) time, O(1) space)
The simplest idea is to count how many times each value appears. Iterate through the array once and maintain three counters for 0, 1, and 2. Then iterate through the array again and overwrite values: first fill count0 positions with 0, the next count1 positions with 1, and the remaining with 2. This approach uses two linear passes over the array, giving O(n) time complexity with constant extra memory (O(1)). It’s easy to implement and works well when modification of the array is allowed. Conceptually, it’s a simplified version of sorting where the value range is very small.
Approach 2: Dutch National Flag Algorithm (O(n) time, O(1) space)
The optimal solution uses a three-pointer technique known as the Dutch National Flag algorithm. Maintain three indices: low, mid, and high. The region before low contains 0s, the region after high contains 2s, and the current element is examined at mid. While iterating, swap values to move 0s left and 2s right. If nums[mid] == 0, swap with low and increment both pointers. If it’s 1, just move mid. If it’s 2, swap with high and decrement high. The key insight: each swap places at least one element in its final position. The array is processed in a single pass with constant space.
This approach heavily relies on pointer manipulation and conditional swaps, making it a classic example of the two pointers pattern applied to an array. Since the algorithm processes each element at most once, the total runtime stays O(n) and memory usage remains O(1).
Recommended for interviews: Interviewers typically expect the Dutch National Flag solution. The counting method shows you understand the constraints and can optimize beyond general sorting. However, the three-pointer algorithm demonstrates deeper control over in-place array manipulation and linear-time partitioning. Many interviewers follow up by asking why the single-pass approach works and how the pointer invariants maintain the correct partition.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed pointers.
| Approach | Complexity |
|---|---|
| Counting Sort Approach | Time Complexity: O(n), where n is the number of elements in the array. |
| Dutch National Flag Problem Solution | Time Complexity: O(n), where n is the length of the array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Sort | O(n) | O(1) | Simple implementation when two passes over the array are acceptable |
| Dutch National Flag (Three Pointers) | O(n) | O(1) | Preferred interview solution; single-pass in-place partitioning |
Sort Colors - Quicksort Partition - Leetcode 75 - Python • NeetCode • 106,865 views views
Watch 9 more video solutions →Practice Sort Colors with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor