Sort Colors - Leetcode Solution

Problem Statement: 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: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Algorithm: The problem can be solved using a two-point approach. We need to choose two pointers namely low and high. We keep low pointer at the beginning and high pointer at the end of an array and then we traverse the array from the starting index until the low pointer reaches the end of the array. At each step, we compare the element at the low index with the element at the high index. If the element at the low index is 2, we swap it with the element at the high index and decrement the high index by 1. If the element at the low index is 0, we swap it with the element at the low index and increment the low index by 1. If the element at the low index is 1, we simply increment the low index by 1. This way we keep the red elements at the beginning, white elements in the middle, and blue elements at the end.

Code:

class Solution { public: void sortColors(vector<int>& nums) { int low = 0, high = nums.size() - 1, mid = 0; while(mid <= high) { if(nums[mid] == 0) { swap(nums[low], nums[mid]); low++; mid++; } else if(nums[mid] == 2) { swap(nums[high], nums[mid]); high--; } else { mid++; } } } };

Time Complexity: The time complexity of the above solution is O(n) as we need to traverse the array only once.

Space Complexity: The space complexity of the above solution is O(1) as we are not using any extra space for sorting.

1