# Sort Colors

**Problem Statement**

**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:

- 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. - If the
*mid*pointer reaches an element with value 1 then simply increment the*mid*pointer by one - 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!