Sort Colors (Dutch National Flag Problem)

Two Pointers

Problem

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

For example:

Input: [1, 0, 2, 1, 0]
Output: [0 0 1 1 2]

Input: [2, 2, 0, 1, 2, 0]
Output: [0 0 1 2 2 2 ]

Solution

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        i=0
        low = 0
        high = len(nums)-1
        
        while i <= high:
            if nums[i] == 0:
                t = nums[low]
                nums[low] = nums[i]
                nums[i] = t
                low+=1
                i+=1
            elif nums[i] == 1:
                i+=1
            elif nums[i] == 2: 
                te = nums[high]
                nums[high] = nums[i]
                nums[i] = te
                high-=1
            
#Two pointer approach: pointing two pointers at the first 
#and last index of the array and have another pointer
#iterating through the array sorting the numbers in place

#Dont increment index at elif nums[i] == 2 cause we 
#don't know if the swicthed number is in the right 
place

#Time: O(n)
#Space: O(n)