ONE HINT AWAY

13Three-way partitionArrays and hashing

Three-way partition

Only three kinds of values to group in place: three pointers, one pass.

  • 7 slides
  • Java · Python · C++ · JavaScript
  • 3 practice problems
Three-way partition, slide 1 of 7
Three-way partition, slide 3 of 7
Three-way partition, slide 4 of 7
Three-way partition, slide 5 of 7
Three-way partition, slide 6 of 7
Three-way partition, slide 7 of 7
1 / 7

Clue: only three kinds of values to group, in place. Worked example: LeetCode 75, Sort Colors (Medium): 0s first, then 1s, then 2s, in one pass.

Example used on every slide: nums = [1, 0, 2, 2, 1, 0] → [0, 0, 1, 1, 2, 2] in 6 steps.

The idea

Three pointers split the array into four zones:

  • nums[0 .. low-1] are all 0
  • nums[low .. mid-1] are all 1
  • nums[mid .. high] are not checked yet
  • nums[high+1 .. end] are all 2

mid reads one number at a time. A 0 is swapped to low, a 2 is swapped to high, a 1 stays. The loop ends when mid passes high, because then nothing is left to check.

Pseudocode

Pseudocode · any language
low = 0                   // next 0 goes here
mid = 0                   // number to check
high = length(nums) - 1   // next 2 goes here
while mid <= high:
    if nums[mid] == 0:
        swap nums[low], nums[mid]
        low = low + 1
        mid = mid + 1
    else if nums[mid] == 1:
        mid = mid + 1
    else:
        swap nums[mid], nums[high]
        high = high - 1   // mid stays

The trap: after swapping with high, do not move mid. The number that came back from high has not been checked yet. On [1, 2, 0], moving mid there too returns [1, 0, 2]. Keep mid where it is, and it checks that 0 next: [0, 1, 2].

Code

public class Solution {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int t = nums[low]; nums[low] = nums[mid]; nums[mid] = t;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int t = nums[mid]; nums[mid] = nums[high]; nums[high] = t;
                high--; // mid stays: the number from high is unchecked
            }
        }
    }
}

Complexity

  • Time: O(n). Every step either moves mid forward or moves high back, so the loop runs at most n times.
  • Space: O(1). Only three pointers; the array is sorted in place.
  • A comparison sort would take O(n log n). Counting the 0s, 1s and 2s and rewriting the array is also O(n), but takes two passes.

How it was tested

All four versions were compiled and run against a brute-force answer (the built-in sort) on 1,200 inputs: 1,186 random arrays of length 0 to 12, one random array of length 300 (the LeetCode maximum), and the edge cases empty, single element, all equal, already sorted, reversed, [2, 0, 1], [1, 2, 0] and [2, 1, 0]. All four matched on every input. Re-run on 31 October 2026 on 3,004 more inputs (3,000 random arrays of length 0 to 12, the example, [2, 1, 0], [1, 2, 0] and the empty array): all four matched the built-in sort on every one.

Practice

Try these in order. Open the worked example first if you got stuck on the slides.