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 colors red, white, and blue, respectively.
You must solve the problem without using the library’s sort function.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [2, 0, 2, 1, 1, 0]
Output:
Sorted colors: [0, 0, 1, 1, 2, 2]
Input:
nums = [2, 0, 1]
Output:
Sorted colors: [0, 1, 2]
Sort Colors Solution in C++:
The idea is to use the Dutch National Flag algorithm, which is a three-way partitioning algorithm that sorts an array of three distinct elements. We use three pointers (low, mid, and high) to partition the array into three sections: the section of 0s, the section of 1s, and the section of 2s. We iterate through the array, and depending on the value of the element, we move it to its correct section while updating the pointers.
#include <iostream>
#include <vector>
void sortColors(std::vector<int>& nums) {
int low = 0; // Pointer to track the section of 0s.
int mid = 0; // Pointer to track the section of 1s.
int high = nums.size() - 1; // Pointer to track the section of 2s.
while (mid <= high) {
if (nums[mid] == 0) {
std::swap(nums[low], nums[mid]); // Move 0 to the section of 0s.
low++; // Move low pointer to the right.
mid++; // Move mid pointer to the right.
} else if (nums[mid] == 1) {
mid++; // Move mid pointer to the right.
} else if (nums[mid] == 2) {
std::swap(nums[mid], nums[high]); // Move 2 to the section of 2s.
high--; // Move high pointer to the left.
}
}
}
int main() {
std::vector<int> nums1 = {2, 0, 2, 1, 1, 0};
std::vector<int> nums2 = {2, 0, 1};
sortColors(nums1);
sortColors(nums2);
std::cout << "Sorted colors: [";
for (int num : nums1) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
std::cout << "Sorted colors: [";
for (int num : nums2) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the size of the input vector nums. This is because we use a two-pointer approach that traverses the array once.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The sorting is performed in-place, modifying the original array.