75. Sort Colors

Intution

This is a classic Dutch National Flag problem. We want to sort the array in-place such that all:

• 0s (red) come first,

• followed by 1s (white),

• followed by 2s (blue).

Instead of counting and rewriting, we use three pointers to partition the array as we iterate through it.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public class Solution {
    private void swap(int[] nums, int i , int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void sortColors(int[] nums) {
        int low = 0; // All 0s will go before this index
        int high = nums.length - 1; // All 2s will go after this index
        int mid = 0; // Iterator

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, mid, low);
                mid++;
                low++;
            } else if (nums[mid] == 2) {
                swap(nums, mid, high);
                high--;
            } else {
                mid++;
            }
        }
    }
}