LeetCode Solution 75 - Sort Colors

 Problem Statement:

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent red, white, and blue, respectively.

You must solve this problem without using the built-in sort() function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

---

Optimal Approach: Dutch National Flag Algorithm

Explanation:

The Dutch National Flag algorithm, also known as the Three-Pointer Approach, is the most efficient way to solve this problem. It sorts the array in a single pass (O(n) time complexity).

Algorithm:

1. Maintain three pointers: low, mid, and high.
2. low tracks the position for 0s, mid traverses the array, and high tracks the position for 2s.
3. As mid iterates, swap elements accordingly:
   • If nums[mid] == 0, swap nums[mid] with nums[low] and move both low and mid forward.
   • If nums[mid] == 1, just move mid forward.
   • If nums[mid] == 2, swap nums[mid] with nums[high] and decrease high (without moving mid).

---

LeetCode-Compatible C++ Code Implementation:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums[low], nums[mid]);
                low++; mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

---

Step-by-Step Execution:

Consider nums = [2,0,2,1,1,0]

1. Initial state: low = 0, mid = 0, high = 5.
2. First iteration: Swap nums[mid] (2) with nums[high] (0). Move high--.
   • nums = [0,0,2,1,1,2]
3. Second iteration: Swap nums[mid] (0) with nums[low] (0). Move low++ and mid++.
   • nums = [0,0,2,1,1,2]
4. Continue iterations until mid > high.
5. Final output: [0,0,1,1,2,2].

---

Alternative Approaches:

1. Brute Force - Counting Sort (O(n) + O(n))

• Count occurrences of 0, 1, and 2.
• Overwrite nums with the counted values.
• Time Complexity: O(n)
• Space Complexity: O(1)

2. Using sort() Function (O(n log n))

• Simply use sort(nums.begin(), nums.end()).
• Not optimal due to O(n log n) complexity.

---

Best Solution & Why It’s Best:

Approach	Time Complexity	Space Complexity	Reason
Dutch National Flag (Optimal)	O(n)	O(1)	Single-pass, in-place sorting
Counting Sort	O(n)	O(1)	Two-pass sorting
Built-in Sort	O(n log n)	O(1)	Not optimal for a three-value sorting problem

---

Complexity Analysis:

Dutch National Flag Algorithm

• Time Complexity: O(n)
• Space Complexity: O(1) (in-place sorting)

---

Conclusion:

The Dutch National Flag Algorithm is the most efficient way to sort the colors with O(n) time complexity. It ensures a stable in-place sorting of 0s, 1s, and 2s efficiently.

Similar Problems for Practice:

• Sort an Array
• Sort List
• Wiggle Sort

---