Problem Overview

You are given an integer array nums with n elements, where each element is 0, 1, or 2.
You need to sort the array in-place so that all 0s come first, followed by all 1s, and then all 2s.

This problem is also known as the Dutch National Flag problem, introduced by Edsger W. Dijkstra.

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]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

---

Intuition / Approach

The array only contains three distinct values (0, 1, and 2).
The goal is to arrange them in sorted order without using extra space and without library sort functions.

There are multiple approaches, but the Dutch National Flag Algorithm is the most efficient and elegant solution.

The algorithm uses three pointers:

• low for the position of next 0,
• mid for current element under consideration,
• high for the position of next 2.

The idea is to partition the array into three sections:

• [0 ... low-1] contains all 0s,
• [low ... mid-1] contains all 1s,
• [high+1 ... end] contains all 2s.

We iterate through the array using mid and decide where to place each element based on its value.

---

Step-by-Step Algorithm Explanation

1. Initialize: low = 0 mid = 0 high = nums.length - 1
2. Traverse while mid <= high:
   • If nums[mid] == 0:
     • Swap nums[low] and nums[mid].
     • Increment both low and mid (as both positions are now sorted).
   • If nums[mid] == 1:
     • Just move mid forward since 1s are already in the middle section.
   • If nums[mid] == 2:
     • Swap nums[mid] and nums[high].
     • Decrement high (don’t move mid immediately because the swapped element needs to be checked).
3. Continue until mid > high.

After the loop, the array will be sorted in-place.

---

Example Walkthrough

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

Step	low	mid	high	Array State	Action
1	0	0	5	[2,0,2,1,1,0]	nums[mid]=2 → swap(mid,high) → [0,0,2,1,1,2], high=4
2	0	0	4	[0,0,2,1,1,2]	nums[mid]=0 → swap(low,mid) → [0,0,2,1,1,2], low=1, mid=1
3	1	1	4	[0,0,2,1,1,2]	nums[mid]=0 → swap(low,mid) → [0,0,2,1,1,2], low=2, mid=2
4	2	2	4	[0,0,2,1,1,2]	nums[mid]=2 → swap(mid,high) → [0,0,1,1,2,2], high=3
5	2	2	3	[0,0,1,1,2,2]	nums[mid]=1 → mid=3
6	2	3	3	[0,0,1,1,2,2]	nums[mid]=1 → mid=4

Loop ends → final array [0,0,1,1,2,2].

---

Java Code Implementation

public class Solution {
    public void sortColors(int[] nums) {
        int low = 0;              // Pointer for next position of 0
        int mid = 0;              // Current index
        int high = nums.length - 1; // Pointer for next position of 2
        
        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap nums[low] and nums[mid]
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++; // Move forward since 1 is already in the middle section
            } else {
                // nums[mid] == 2
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }
}

---

Complexity Analysis

1. Time Complexity:
   Each element is examined at most once, resulting in O(n) time.
2. Space Complexity:
   Sorting is done in-place using constant extra space → O(1).

---

Alternative Approaches

1. Counting Sort (Two-pass):
   • Count number of 0s, 1s, and 2s.
   • Rewrite the array based on counts.
   • Time: O(n), Space: O(1).
   • Less efficient for in-place single-pass requirement.
2. Built-in Sort:
   • You could call Arrays.sort(nums) but that violates the problem constraint (“in-place and one-pass”).
   • Also has O(n log n) time complexity.