LC 0075 [M] Sort Colors (Dutch National Flag Partition) - ALawliet/algorithms GitHub Wiki

3-way partition around the middle [w]

T: O(n)
S: O(1)

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