Skip to main content
Two Pointer

Three-Way Partition

Three pointers split the array into three regions in a single pass. The Dutch National Flag problem: sort an array of 0s, 1s, and 2s using low, mid, and high pointers.

O(n)
·
O(1)

How It Works

Three-way partitioning, popularized by Dijkstra's Dutch National Flag problem, sorts an array of three distinct categories in one pass. Three pointers carve the array into four zones: everything before low is category 0, between low and mid is category 1, after high is category 2, and mid-to-high is unexplored. Examine the element at mid: swap it to the low zone, leave it, or swap it to the high zone accordingly.

A counting sort would need two passes and per-category tallies; a comparison sort costs O(n log n). The flag partition finishes in a single O(n) sweep with O(1) space, and the same partitioning idea underlies quicksort's three-way variant for arrays with many duplicates.

Step-by-Step Visualization

Three-way partition: 0s left, 1s middle, 2s right
mid
2
0
0
1
2
2
1
3
1
4
hi
0
5
nums[mid]2 → swap with hi
1/5

Code

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

  while (mid <= high) {
    if (nums[mid] == 0) {
      int tmp = nums[low]; nums[low] = nums[mid]; nums[mid] = tmp;
      low++; mid++;
    } else if (nums[mid] == 1) {
      mid++;
    } else {
      int tmp = nums[mid]; nums[mid] = nums[high]; nums[high] = tmp;
      high--;
    }
  }
}

// Example: sortColors(new int[]{2,0,2,1,1,0}) → [0,0,1,1,2,2]

Tips & Gotchas

1Use three pointers: low, mid, high to partition into 3 regions
2Elements before low are 0s, between low and mid are 1s, after high are 2s
3Only increment mid when swapping with low; decrement high when swapping with high

Practice Problems

  • 1Sort Colors
  • 2Partition Array According to Given Pivot
  • 3Sort Array By Parity II
  • 4Wiggle Sort II

About the Two Pointer Pattern

Use two index variables that move through the array strategically. They might start at opposite ends and converge, or both start at the beginning with one moving faster. This avoids nested loops.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

Why doesn't mid advance after swapping with the high pointer?

The element swapped in from the high side is unexamined — it could belong to any of the three categories. After a swap with low, however, mid can advance safely, because the low zone only ever hands back a middle-category element that mid previously passed over.

Can three-way partition handle more than three categories?

Not directly in one pass with this pointer scheme; it relies on there being exactly three buckets with a total order. For k categories, counting sort with a frequency array and a rebuild pass is the standard O(n + k) alternative.