Sort 0s, 1s and 2s

#algorithms #interview #computerscience #tutorial

Hi everyone!
Today I solved a very interesting array problem where we need to sort an array containing only 0s, 1s, and 2s — but without using the built-in sort function.

Problem

Given an array of 0s, 1s, and 2s, sort it in ascending order.

Example:
Input: [0, 1, 2, 0, 1, 2]

Output: [0, 0, 1, 1, 2, 2]

My Approach

At first, sorting seemed like the obvious solution.

But the problem specifically says:
Don’t use built-in sort
So I looked for a better approach

That’s when I learned about the Dutch National Flag Algorithm.

Logic

We use three pointers:

low → for placing 0s
mid → current element
high → for placing 2s

Rules:

If element is 0 → swap with low, move both
If element is 1 → just move mid
If element is 2 → swap with high, move high

Code (Python)
class Solution:
def sort012(self, arr):
low, mid, high = 0, 0, len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr

Time & Space Complexity