Sort Colors

Problem Statement

Sort Colors - LeetCode

Naive Solution

The first approach for this problem that comes to mind is to sort the array. Thus approach will work in O(nlogn) if we sorting techniques like merge sort. So that’s the naive solution to this problem.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        nums.sort()

Time Complexity: O(nlogn)

Space Complexity: No extra space

Efficient Solution

The efficient approach is to take 3 pointers i.e. low, high, and mid. Start the low and mid pointer from the 0th index and the high pointer to the last index. Now consider 3 cases:

1. As soon as the mid pointer reaches an element with a value of 0, just swap it with the low pointer value and increment both the pointers by one.
2. If the mid pointer reaches an element with value 1 then simply increment the mid pointer by one
3. If the mid pointer reaches an element with value 2 then swap it with the high pointer value and decrement the high pointer.

This will go on until mid ≤ high.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low = 0
        high = len(nums) - 1
        mid = 0
        while (mid <= high):
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[high], nums[mid] = nums[mid], nums[high]
                high -= 1
        return nums

In this solution, we are making sure that all the elements on the left of low are 0 and on the right of high are 2.

Time Complexity: O(n)

Space Complexity: O(1)

That’s all about this problem. Comment down if you have any doubt or want me to write a blog on any specific problem.

Keep solving!