Watch 10 video solutions for Sort Colors, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 106,865 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’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.
| 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 |