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

$ curl repovive.com/roadmaps/fundamental-algorithms/two-pointers/example-sort-colors

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/two-pointers/example-sort-colors

Repovive

Example - Sort Colors - Two Pointers | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Example - Sort Colors

Dutch National Flag problem.

Problem: Sort array with values $0$ , $1$ , $2$ in one pass.

Approach: Dutch National Flag with three pointers.

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

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

Time: $O(n)$ . Space: $O(1)$ .