Watch 10 video solutions for Sort Colors, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 139,332 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |