Given an array nums containing only 0s, 1s, and 2s. Sort nums in ascending order in-place.
Example 1
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: All 0s are placed first, followed by all 1s, and then all 2s.
Example 2
Input: nums = [2, 0, 1]
Output: [0, 1, 2]
Explanation: The values are rearranged in ascending order.
Brute Force Approach
A direct solution is to use a standard sorting routine. Since numeric ascending order places 0 before 1 and 1 before 2, the sorted array automatically satisfies the requirement.
This method treats the input like a general array of numbers. It is simple and reliable, but it does not use the special fact that only three values can appear.
Algorithm
Apply the language's numeric ascending sort to the given array.
Let the sorting routine rearrange all values so smaller categories appear before larger categories.
Keep the sorted values in the same array, so no separate answer array is required.
nums now contains all
0s, then all1s, then all2s.
Dry Run
Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts nums containing only 0, 1, and 2. void sortColors(vector<int>& nums) { // Sort the array in numeric ascending order. sort(nums.begin(), nums.end()); }};// Driver codeint main() { vector<int> nums = {2, 0, 2, 1, 1, 0}; // instance for class Solution Solution sol; sol.sortColors(nums); // Print the array after in-place sorting. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n) because a general comparison-based sorting routine is used.
Space Complexity: O(1) to O(n) auxiliary space depending on the language and sorting implementation.
Optimal Approach 1
Instead of comparing values as if many different numbers were possible, the fixed value range can be used directly. Count how many 0s, 1s, and 2s appear, then overwrite the array with exactly that many values in sorted order.
Algorithm
Create three counters for
0,1, and2; a one-element array simply increases one of these counters.Traverse the array once and increase the counter that matches each value.
Start writing from the first position and place all counted
0s.Continue from the next free position and place all counted
1s, then all counted2s.Stop after exactly
nvalues have been written back into nums.
Dry Run
Optimal 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts nums containing only 0, 1, and 2. void sortColors(vector<int>& nums) { int zeroCount = 0; int oneCount = 0; int twoCount = 0; // Count how many times each allowed value appears. for (int value : nums) { // Increase the counter that matches the current value. if (value == 0) { zeroCount++; } else if (value == 1) { oneCount++; } else { twoCount++; } } int index = 0; // Write all zeroes first. for (int count = 0; count < zeroCount; count++) { nums[index] = 0; index++; } // Write all ones after the zeroes. for (int count = 0; count < oneCount; count++) { nums[index] = 1; index++; } // Write all twos at the end. for (int count = 0; count < twoCount; count++) { nums[index] = 2; index++; } }};// Driver codeint main() { vector<int> nums = {2, 0, 2, 1, 1, 0}; // instance for class Solution Solution sol; sol.sortColors(nums); // Print the array after in-place sorting. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because the array is counted once and then overwritten once.
Space Complexity: O(1) auxiliary space because only three counters and one write position are stored.
Optimal Approach 2
Think of the array as three regions. The left side is reserved for confirmed 0s. The right side is reserved for confirmed 2s. Everything between them is still unknown and needs to be classified. Since 1 belongs between 0 and 2, it can stay in the middle once it is found.
Three pointers protect these regions. The left pointer marks where the next 0 should go. The right pointer marks where the next 2 should go. The current pointer inspects the unknown region. When a 0 is found, it is moved to the left side. When a 2 is found, it is moved to the right side. When a 1 is found, the middle region simply grows.
The only careful detail is the 2 case. After swapping with the right side, the value brought into the current position is still unknown. That value must be inspected before moving forward. This is the reason the current pointer moves after handling 0 and 1, but not immediately after handling 2.
Algorithm
Treat the array as four parts: confirmed
0s, confirmed1s, unknown values, and confirmed2s.Place the left boundary at the first index, the current position at the first index, and the right boundary at the last index.
If the current value is
0, swap it into the left region and move both the left boundary and current position forward.If the current value is
1, leave it in the middle region and move only the current position forward.If the current value is
2, swap it into the right region and move only the right boundary backward because the swapped-in value is still unknown.Stop when the current position crosses the right boundary; the unknown region is empty, so the whole array is sorted.
Dry Run
Dutch National Flag
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Sorts nums containing only 0, 1, and 2. void sortColors(vector<int>& nums) { int left = 0; int current = 0; int right = nums.size() - 1; // Classify every value inside the unknown region. while (current <= right) { // Move 0s left, leave 1s in the middle, and move 2s right. if (nums[current] == 0) { swap(nums[left], nums[current]); left++; current++; } else if (nums[current] == 1) { current++; } else { swap(nums[current], nums[right]); right--; } } }};// Driver codeint main() { vector<int> nums = {2, 0, 2, 1, 1, 0}; // instance for class Solution Solution sol; sol.sortColors(nums); // Print the array after in-place sorting. for (int value : nums) { cout << value << ' '; } cout << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n) because each value is classified at most a constant number of times.
Space Complexity: O(1) auxiliary space because only three positions are stored and sorting happens in-place.
Interview follow-up Questions
It sorts the array in linear time and constant auxiliary space. Since every element must be inspected at least once in the general case, O(n) time is the best possible bound.
Be the first to add a comment.