3 Pointers, One Pass: The Smart Sorting Trick

#java #programming #coding #beginners

Sorting usually means:

O(n log n)
Extra space

But what if the array contains only 3 distinct values?

You can sort it in:

O(n) time
O(1) space
Single pass

That’s the Dutch National Flag Algorithm.

Core Idea

Use three pointers:

low → boundary for 0s
mid → current element
high → boundary for 2s

Implementation

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

while (mid <= high) {
    switch (nums[mid]) {
        case 0:
            swap(nums, low, mid);
            low++; mid++;
            break;

        case 1:
            mid++;
            break;

        case 2:
            swap(nums, mid, high);
            high--;
            break;
    }
}

}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

How It Works

At each step: