Back to Problem
Official 2437 views

Editorial: Sort Colors (Dutch Flag)

by admin ·

24

1 Intuition

Three regions: zeros, ones, unknown, twos.

2 Approach

Dijkstra's Dutch National Flag: swap 0s to the front, 2s to the back, and skip 1s.

3 Complexity Analysis

Time O(n), Space O(1).

4 Solution Code 

class Solution:
    def sortColors(self, nums: list[int]) -> list[int]:
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1; mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1
        return nums

5 Code Walkthrough

The reference solution below implements the approach step by step.