In this task, I worked on sorting an array that contains only 0s, 1s, and 2s. Instead of using a normal sorting method, I used a more efficient approach that sorts the array in a single pass.
What I Did:
I created a function called sort012 that takes an array of 0s, 1s, and 2s and returns the sorted array.
For example:
Input: [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
How I Solved It:
To solve this, I used three pointers:
- low → to place 0s
- mid → to traverse the array
- high → to place 2s
I started all pointers at the beginning except high, which starts at the end.
Then I used a loop to go through the array:
If the element is 0 → swap it with the low position and move both low and mid
If the element is 1 → just move mid
If the element is 2 → swap it with the high position and move high
How It Works:
This method works by using three pointers to keep track of where each type of element should go.
The low pointer marks the position where the next 0 should be placed, the mid pointer is used to scan through the array, and the high pointer marks where the next 2 should go.
As the loop runs, the algorithm checks the value at the mid position and swaps it with either the low or high position when needed. This gradually moves all 0s to the beginning, 1s to the middle, and 2s to the end, resulting in a sorted array.
CODE:
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