dutch national flag problem solution

dutchFlag.py

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        
        start, end = 0, len(nums)-1
        
        i = start
        while i <= end:
            if nums[i] == 0:
                nums[start], nums[i] = nums[i] ,nums[start]
                start += 1
                # traveller pointer must never be behind start pointer
                if start > i: i = start
            elif nums[i] == 2:
                nums[end], nums[i] = nums[i] ,nums[end]
                end -= 1
            else:
                i += 1






class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, left, right = 0, 0, len(nums)-1
        
        while i <= right:
            if nums[i] == 0 and i >= left:
                nums[i], nums[left] = nums[left], nums[i]
                left += 1
            elif nums[i] == 2 and i <= right:
                nums[i], nums[right] = nums[right], nums[i]
                right -= 1
            else:
                i += 1

https://leetcode.com/problems/sort-colors

Quick explanation:

• There are two boundary pointers: left and right

• anything before left must be 0

• anything after right must be 2

• There's one iterating pointer i.e. i

• so we start from left and keep moving till we reach right (out of bounds region for left and right/ unknown region for i)

• If i comes across 0: "Hey, left seems your item is misplaced, take this within your boundary". So we swap item at i and left and left moves one step ahead to mark the new boundary

• Same things happens between right and i, if i comes across 2

Now whenever a swap happens, i gets a new unknown item in exchange, hence it doesn't move to ensure the new item is explored in next iteration of the loop. When a swap doesn't happen, i knows the item is at right place so it just moves a step forward