Three Number Sort

Tags

Three Number Sort

Category

Sorting

Difficulty

Medium

Problem Statement

Given an array of integers that only contains three distinct values and a separate array defining the desired order of those three values, sort the main array in-place according to that order. For example, given [1, 0, 0, -1, -1, 0, 1, 1] and order [0, 1, -1], the result should be [0, 0, 0, 1, 1, 1, -1, -1].

Intuition

This is a variant of the Dutch National Flag problem. Since there are only three distinct values, we can partition the array in a single pass using three pointers. One pointer tracks where the next "first" value should go, another tracks where the next "third" value should go, and a scanning pointer moves through the array.

Approach

  1. Let the three values in order be first, second, and third.
  2. Initialize three pointers: low = 0, mid = 0, high = length - 1.
  3. While mid <= high:
    • If array[mid] == first: swap array[low] and array[mid], increment both low and mid.
    • If array[mid] == second: just increment mid (it is in the correct middle zone).
    • If array[mid] == third: swap array[mid] and array[high], decrement high (do not increment mid because the swapped element needs inspection).
  4. Return the array.

Pseudocode

function threeNumberSort(array, order):
    first = order[0]
    third = order[2]
    low = 0
    mid = 0
    high = length(array) - 1
    while mid <= high:
        if array[mid] == first:
            swap(array[low], array[mid])
            low += 1
            mid += 1
        else if array[mid] == third:
            swap(array[mid], array[high])
            high -= 1
        else:
            mid += 1
    return array

Time & Space Complexity

  • Time: O(n) — Single pass through the array. Each element is processed at most twice (once by mid, potentially once more after a swap from high).
  • Space: O(1) — Only three pointer variables are used.

Key Insights

  • This is essentially the Dutch National Flag algorithm attributed to Dijkstra.
  • When swapping with high, we do not advance mid because the element swapped from high has not been inspected yet.
  • When swapping with low, we can safely advance mid because low <= mid and everything before mid has already been categorized.
  • An alternative two-pass approach: first move all first values to the front, then move all third values to the back.

Edge Cases

  • Array contains only one of the three values — all pointers converge quickly.
  • Array contains only two of the three values — one partition remains empty.
  • Array is already sorted in the desired order — mid advances through without swaps.
  • Single-element array — already sorted.

Linked mentions