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 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.
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.
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed 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:
nums[k] = 0, then swap it with nums[i+1], then increment both i and k by 1;nums[k] = 2, then swap it with nums[j-1], then decrement j by 1;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).
| 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. |
| Three Pointers | — |
| Approach | Time | Space | When 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 Algorithm | O(n) | O(1) | Best for interviews; single-pass in-place partitioning |
Sort Colors - Quicksort Partition - Leetcode 75 - Python • NeetCode • 139,332 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