Task – Sort an Array of 0s, 1s and 2s (Without Using Built-in Sort)

Problem Statement

Given an array arr[] containing only 0s, 1s, and 2s, sort the array in ascending order.

You must not use any built-in sorting function.

Example 1

Input:

arr[] = [0, 1, 2, 0, 1, 2]

Output:

[0, 0, 1, 1, 2, 2]

Explanation:
All 0s appear first, followed by 1s, then 2s.

Example 2

Input:

arr[] = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]

Output:

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]

Explanation:
The elements are rearranged in ascending order.

Constraints
1 ≤ arr.size() ≤ 10^5
0 ≤ arr[i] ≤ 2
Approach

Since the array contains only three distinct values (0, 1, 2), we can solve this efficiently using three pointers.

We maintain:

low → position for next 0
mid → current element being checked
high → position for next 2
Working Logic
If arr[mid] == 0
Swap arr[low] and arr[mid], increment both low and mid
If arr[mid] == 1
Just move mid forward
If arr[mid] == 2
Swap arr[mid] and arr[high], decrement high

This ensures:

Left side contains 0s
Middle contains 1s
Right side contains 2s
Time and Space Complexity

Time Complexity: O(n) (Single traversal)
Space Complexity: O(1) (No extra space used)

This satisfies the follow-up condition of one-pass and constant space.

SOLUTION:
class Solution:
def sort012(self, arr):
low = 0
mid = 0
high = 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] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr

Step-by-Step Example Dry Run

For input:

[0, 1, 2, 0, 1, 2]

Initially:

low = 0
mid = 0
high = 5

We move through the array and rearrange elements in one traversal.

Final result:

[0, 0, 1, 1, 2, 2]