Sort an Array of 0s, 1s and 2s

Sorting is one of the fundamental operations in data structures. A common interview problem is sorting an array that contains only three distinct values: 0s, 1s, and 2s.

Problem Statement

Given an array arr[] containing only 0s, 1s, and 2s, sort the array in ascending order without using any built-in sort function.

Example 1:
Input: [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
Example 2:
Input: [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]

Approach: Dutch National Flag Algorithm

The optimal way to solve this problem is by using the Dutch National Flag Algorithm, which works in a single pass and uses constant extra space.

Key Idea
We divide the array into three regions:

Left → all 0s
Middle → all 1s
Right → all 2s

To achieve this, we use three pointers:

low → position to place the next 0
mid → current element under consideration
high → position to place the next 2
Algorithm Steps
Initialize:
low = 0
mid = 0
high = n - 1
Traverse the array while mid <= high:
If element is 0:
Swap with low
Increment both low and mid
If element is 1:
Move mid forward
If element is 2:
Swap with high
Decrement high (do not increment mid here)
** Python Implementation 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

Time and Space Complexity
Time Complexity: O(n)
(The array is traversed only once)
Space Complexity: O(1)
(No extra space is used)

** Common Mistakes**
Returning a new array instead of modifying in place
Using built-in sorting functions
Incrementing mid after swapping with high
Using extra memory unnecessarily

*Alternative Approach (Counting Method)
*
Another approach is to count the number of 0s, 1s, and 2s, and then overwrite the array accordingly. However, this requires two passes, whereas the Dutch National Flag algorithm solves it in a single pass.

** Conclusion**

The Dutch National Flag Algorithm is an elegant and efficient solution for sorting arrays with limited distinct values. It is frequently asked in coding interviews and is a great example of optimizing both time and space complexity.

Mastering such in-place algorithms can significantly improve problem-solving skills in data structures and algorithms.