LeetCode #75 - Sort Colors

📝 Introduction

Given an array nums with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

*Constraints typically include:

• You must solve this problem without using the library’s sort function.
• The array contains only values 0, 1, and 2.*

💡 Approach & Key Insights

The problem can be solved through various approaches. Though sorting is a valid but not expected solution, we can explore better and optimal methods by leveraging the limited number of distinct values (0, 1, 2). This allows for more efficient counting or pointer-based techniques like the Dutch National Flag algorithm.

🛠️ Breakdown of Approaches

1️⃣ Brute Force / Naive Approach

• Explanation: Use the built-in sorting algorithm to sort the array. This works since the array contains only 0, 1, and 2, and sorting would naturally arrange them.
• Time Complexity: O(n log n) – standard sorting complexity.
• Space Complexity: O(1) – assuming in-place sort.
• Example/Dry Run:

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

2️⃣ Better Approach

• Explanation: Count the number of 0s, 1s, and 2s in one pass. Then overwrite the array in a second pass by placing the right number of 0s, 1s, and 2s.
• Time Complexity: O(n) – 2 passes through the array.
• Space Complexity: O(1) – constant space for counters.
• Example/Dry Run:

1
Input: [2, 0, 2, 1, 1, 0]
2
Step 1: Count → count_0 = 2, count_1 = 2, count_2 = 2
3
Step 2: Overwrite:
4
[0, 0, 1, 1, 2, 2]

3️⃣ Optimal Approach

• Explanation: Use the Dutch National Flag algorithm with three pointers (low, mid, high). Rearrange elements in a single pass.
• Time Complexity: O(n) – single pass.
• Space Complexity: O(1) – in-place.
• Example/Dry Run:

1
Input: [2, 0, 2, 1, 1, 0]
2
Initial: low = 0, mid = 0, high = 5
3

4
Step-by-step:
5
mid = 0, nums[mid] = 2 → swap(nums[mid], nums[high]) → high--
6
mid = 0, nums[mid] = 0 → swap(nums[low], nums[mid]) → low++, mid++
7
mid = 1, nums[mid] = 0 → swap(nums[low], nums[mid]) → low++, mid++
8
mid = 2, nums[mid] = 2 → swap(nums[mid], nums[high]) → high--
9
mid = 2, nums[mid] = 1 → mid++
10
mid = 3, nums[mid] = 1 → mid++
11

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

📊 Complexity Analysis

📉 Optimization Ideas

The Dutch National Flag algorithm is already optimal — it solves the problem in a single traversal with constant space. No further optimization is necessary.

📌 Example Walkthroughs & Dry Runs

1
Example:
2
Input: [2, 0, 1]
3
Initial: low = 0, mid = 0, high = 2
4

5
1. nums[mid] = 2 → swap(nums[mid], nums[high]) → [1, 0, 2], high--
6
2. nums[mid] = 1 → mid++
7
3. nums[mid] = 0 → swap(nums[low], nums[mid]) → [0, 1, 2], low++, mid++
8

9
Output: [0, 1, 2]

🔗 Additional Resources

• Dutch National Flag Algorithm
• Python list sorting

Author: Neha Amin Date: 19/07/2025