Sorting - Dutch National Flag (Sort Colors)

Given an array with values 0, 1, and 2, sort them in-place so all 0s come first, then 1s, then 2s. (LeetCode 75 — Sort Colors)

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

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

Three-pointer approach (Dutch National Flag algorithm by Dijkstra): maintain pointers lo, mid, hi. Invariant: arr[0..lo-1]=0, arr[lo..mid-1]=1, arr[hi+1..n-1]=2.

Initialize lo=0, mid=0, hi=n-1.
While mid <= hi: if arr[mid]==0 swap arr[lo] and arr[mid], lo++, mid++.
If arr[mid]==1, just mid++.
If arr[mid]==2, swap arr[mid] and arr[hi], hi-- (do not advance mid).

class Solution { public void sortColors(int[] nums) { int lo = 0, mid = 0, hi = nums.length - 1; while (mid <= hi) { if (nums[mid] == 0) { int tmp = nums[lo]; nums[lo] = nums[mid]; nums[mid] = tmp; lo++; mid++; } else if (nums[mid] == 1) { mid++; } else { int tmp = nums[mid]; nums[mid] = nums[hi]; nums[hi] = tmp; hi--; } } } }

Time Complexity: O(N) — single pass
Space Complexity: O(1) in-place