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?
The Sort Colors problem asks you to reorder an array containing only 0, 1, and 2 so that elements of the same color are grouped together. A straightforward idea is counting occurrences of each value and rewriting the array. While simple, this approach requires two passes over the array.
A more optimal and commonly discussed solution is the Dutch National Flag algorithm. This method uses three pointers to partition the array into three regions representing 0s, 1s, and 2s. By adjusting pointers and swapping elements in a single traversal, the array can be sorted in-place.
This approach is preferred in interviews because it demonstrates mastery of the two-pointer technique and in-place array manipulation. The algorithm runs in linear time and requires constant extra space, making it both efficient and elegant for this problem.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Counting / Frequency Method | O(n) | O(1) |
| Dutch National Flag (Three Pointers) | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
A rather straight forward solution is a two-pass algorithm using counting sort.
Iterate the array counting number of 0's, 1's, and 2's.
Overwrite array with the total number of 0's, then 1's and followed by 2's.
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.
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.
1#include <stdio.h>
2
3void sortColors(int* nums, int numsSize) {
4 int count[3] = {0};
5 for (int i = 0; i < numsSize; i++) {
6 count[nums[i]]++;
7 }
8 int index = 0;
9 for (int i = 0; i < count[0]; i++)
10 nums[index++] = 0;
11 for (int i = 0; i < count[1]; i++)
12 nums[index++] = 1;
13 for (int i = 0; i < count[2]; i++)
14 nums[index++] = 2;
15}
16
17int main() {
18 int nums[] = {2,0,2,1,1,0};
19 int size = sizeof(nums) / sizeof(nums[0]);
20 sortColors(nums, size);
21 for (int i = 0; i < size; i++)
22 printf("%d ", nums[i]);
23 return 0;
24}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.
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), because we only use fixed pointers.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Sort Colors is a common interview problem and has appeared in interviews at top tech companies. It tests understanding of array manipulation, two-pointer techniques, and in-place sorting strategies.
The optimal approach is the Dutch National Flag algorithm. It uses three pointers to partition the array into sections for 0s, 1s, and 2s while traversing the array once. This allows the array to be sorted in-place with O(n) time and O(1) space.
The problem is primarily solved using arrays with pointer manipulation. No additional data structures are required because the algorithm rearranges elements directly within the input array using swaps.
The Dutch National Flag algorithm efficiently partitions elements into three groups using a single pass. Since the array contains only three distinct values, the algorithm can place each element in its correct region without needing extra memory.
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.