LC-75 Sort Colors(Dutch Flag Problem)

You are 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.

Brute Force Solution: -

Approach is straight-forward. Since the array consists of only 0s,1s and 2s, we can count the frequency of them and refill the array with 0s,1s and 2s respectively.

zc = 0, oc = 0, tc = 0
n = nums.size()

for int i = 0 to i < n and i++
    if(nums[i] == 0)
        zc++;
    else if(nums[i] == 1)
        oc++;
    else
        tc++;

for int i = 0 to i + zc and i++
    nums[i] = 0

for int i = zc to i < zc + oc and i++
    nums[i] = 1

for int i = zc + oc to i < zc + oc + tc and i++
    nums[i] = 2

• Time Complexity: O(n)

• Space Complexity : O(1)

Optimal Solution: -

Although the above solution is fine in terms of time and space complexity, but as you can see, we are performing multiple passes. Instead, we can solve this question in a single pass(In-Place) which is the desired solution

• We will maintain 3 regions and we name them as 0-region, 1-region , 2-region. These regions are imaginary just for the sake of solving the problem.

• The zone mid to high is given to us as question.

• Approach is like initialise low = 0, mid = 0 and high = n - 1

• If nums[mid] == 0, simply swap nums[mid] and nums[low]. Now since low to mid - 1 is 1s zone, we have to increment both low and mid. This will be clear if you trace this on paper by drawing the above zones.

• If nums[mid] == 1, simply increment mid.

• If nums[mid] == 2, swap nums[mid] and nums[high] and decrement high.

int low = 0, mid = 0, high = n - 1

while(mid <= high){
    if(nums[mid] == 0){
        swap(nums[mid],nums[low]);
        low++;
        mid++;
    }
    
    else if(nums[mid] == 1)
        mid++;
    
    else{
        swap(nums[mid],nums[high]);
        high--;
    }
}

• Time Complexity: O(n)

• Space Complexity : O(1)