#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/sort-colors-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/sorting-algorithms/sort-colors-implementation

Repovive

Sort Colors - Implementation - Sorting Algorithms | Fundamental Algorithms | Repovive

Repovive.

Sort Colors - Implementation

min

Here is the implementation using the Dutch National Flag algorithm:

function sortColors(nums):
    low = 0
    mid = 0
    high = nums.length - 1

    while mid <= high:
        if nums[mid] == 0:
            swap(nums, low, mid)
            low += 1
            mid += 1
        else if nums[mid] == 1:
            mid += 1
        else:
            swap(nums, mid, high)
            high -= 1

This runs in $O(n)$ O(n) time with $O(1)$ O(1) space (excluding input). Each element is visited at most twice.