Menu

1 / 2

3 Pointers, One Pass: The Smart Sorting Trick

DEV Community·Quipoin·6 months ago
#1nTptpPD
#coding#java#programming#beginners#high
Reading 0:00
15s threshold

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; } }

Enter fullscreen mode

Exit fullscreen mode

}

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:

If 0 → move to left

If 1 → keep in middle

If 2 → move to right

All done in one traversal

The Real Insight

Instead of sorting, we partition the array

This is similar to Quick Sort partitioning.

Key Insights

Three-pointer technique

In-place…

Continue reading — create a free account

Join HashtagPLUS to read full articles, follow hashtags, vote, and join the conversation.