Sort 0s, 1s and 2s - CA08

My Thinking and Approach

---

Introduction

In this problem, I was given an array containing only 0s, 1s, and 2s and asked to sort the array in ascending order.

The important condition is that I should not use any built-in sorting function.

---

Problem Statement

• Given an array arr containing only:

  • 0s
  • 1s
  • 2s

• Sort the array in ascending order

• Condition:

  • Do not use built-in sort
  • Solve in one pass with constant space

---

My Initial Thought

At first, I considered:

• Counting number of 0s, 1s, and 2s
• Rewriting the array based on counts

This approach works but requires two passes.

---

Key Observation

Instead of counting:

• I can sort the array in a single pass
• Use three pointers to place elements correctly

---

Optimized Approach

I decided to use the Dutch National Flag algorithm.

Logic:

• Maintain three pointers:

  • low for 0s
  • mid for traversal
  • high for 2s

• Traverse the array and swap elements based on value

---

My Approach (Step-by-Step)

1. Initialize:

• low = 0
• mid = 0

• high = length - 1

  1. While mid <= high:

• If arr[mid] == 0
  → swap arr[low] and arr[mid]
  → increment low and mid

• If arr[mid] == 1
  → move mid forward

• If arr[mid] == 2
  → swap arr[mid] and arr[high]
  → decrement high

---

Code (Python)

Below is the implementation clearly separated inside a code block:

def sort012(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], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr

---

Example Walkthrough

Input:

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

Steps:

• Move 0s to left
• Keep 1s in middle
• Move 2s to right

Output:

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

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

---

Key Takeaways

• One-pass solution is possible
• Two pointer technique can be extended to three pointers
• No extra space is required

---

Conclusion

This problem helped me understand how to efficiently sort a limited range of values using the Dutch National Flag algorithm.

It is a good example of optimizing both time and space.

---