1. Iterate through the array to count the number of 0s, 1s, and 2s.
2. Iterate through the array a second time to overwrite the array indices based on the counts (e.g., fill the first count0 indices with 0, the next count1 indices with 1, etc.).

Pseudo-code (Counting Approach):

text
count0 = 0, count1 = 0, count2 = 0
for x in nums:
    increment count of x

index = 0
for i from 0 to count0: nums[index++] = 0
for i from 0 to count1: nums[index++] = 1
for i from 0 to count2: nums[index++] = 2

Complexity Analysis:

• Time Complexity: $O(N \log N)$ for generic sort, or $O(2N)$ for the two-pass counting approach.
• Space Complexity: $O(1)$ or $O(\log N)$ depending on the sort implementation.

Why it fails: While the counting approach is technically $O(N)$, it requires two passes over the data. The problem's follow-up explicitly asks for a one-pass algorithm. Furthermore, generic sorting does not utilize the limited cardinality of the input elements (only 3 values).

Core Insight for Sort Colors

The key intuition for solving LeetCode 75 efficiently lies in partitioning the array into three sections. Instead of sorting by comparison, we place elements into their respective "buckets" relative to the array indices.

We can maintain three regions within the array using pointers:

1. Left Region: Strictly contains 0s.
2. Right Region: Strictly contains 2s.
3. Middle Region: Contains 1s and unprocessed elements.

To implement this, we need three pointers:

• low: The boundary for 0s. All elements before this index are 0.
• high: The boundary for 2s. All elements after this index are 2.
• mid: The current element being evaluated.

The algorithm maintains the invariant that at any point during execution:

• nums[0...low-1] are all 0s.
• nums[high+1...n-1] are all 2s.
• nums[low...mid-1] are all 1s.

As mid traverses the array, we examine nums[mid] and swap it into the correct region (low or high) or leave it in the middle if it is a 1. This effectively shrinks the unknown region until the entire array is sorted.

Execution Flow

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

1. Start: low=0, mid=0, high=5.

   • nums[mid] is 2.
   • Swap nums[0] and nums[5]. Array: [0, 0, 2, 1, 1, 2].
   • Decrement high to 4. mid stays 0.

2. Step 2: low=0, mid=0, high=4.

   • nums[mid] is 0.
   • Swap nums[0] and nums[0] (self-swap). Array: [0, 0, 2, 1, 1, 2].
   • Increment low to 1, mid to 1.

3. Step 3: low=1, mid=1, high=4.

   • nums[mid] is 0.
   • Swap nums[1] and nums[1]. Array: [0, 0, 2, 1, 1, 2].
   • Increment low to 2, mid to 2.

4. Step 4: low=2, mid=2, high=4.

   • nums[mid] is 2.
   • Swap nums[2] and nums[4]. Array: [0, 0, 1, 1, 2, 2].
   • Decrement high to 3. mid stays 2.

5. Step 5: low=2, mid=2, high=3.

   • nums[mid] is 1.
   • Increment mid to 3.

6. Step 6: low=2, mid=3, high=3.

   • nums[mid] is 1.
   • Increment mid to 4.

7. End: mid (4) > high (3). Loop terminates. Result: [0, 0, 1, 1, 2, 2].

Proof of Correctness

The correctness relies on the loop invariant involving the three partitions.

• Invariant: [0, low) contains 0s, (high, n-1] contains 2s, and [low, mid) contains 1s.
• Initialization: Initially, all ranges are empty, so the invariant holds trivially.
• Maintenance:
  • When we see a 0, we swap it to low, extending the 0s range and shifting the 1s range.
  • When we see a 1, we extend the 1s range by moving mid.
  • When we see a 2, we swap it to high, extending the 2s range.
• Termination: Since mid increases or high decreases at every step, the unclassified window [mid, high] shrinks to zero. When the loop finishes, the entire array is covered by the three sorted partitions.

Reference Implementation

C++ Solution for LeetCode 75

cpp
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = nums.size() - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap current element to the 0s boundary
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // 1s are in the middle, just move forward
                mid++;
            } else {
                // Swap current element to the 2s boundary
                swap(nums[mid], nums[high]);
                high--;
                // Do not increment mid; we need to check the swapped value
            }
        }
    }
};

Java Solution for LeetCode 75

java
class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int temp = nums[high];
                nums[high] = nums[mid];
                nums[mid] = temp;
                high--;
                // Note: mid is NOT incremented here
            }
        }
    }
}

Python Solution for LeetCode 75

python
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low, mid, high = 0, 0, len(nums) - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else: # nums[mid] == 2
                nums[high], nums[mid] = nums[mid], nums[high]
                high -= 1
                # Do not increment mid here