Sort a tray of three token colours in one pass

Two pointers Mid-level Python 3.13+ Reviewed By Best Latest Apps

Spot the bug

This version sometimes leaves a 0 in the wrong place. Which line is wrong?

  1. def tray(a: list[int]) -> list[int]:
  2. lo, mid, hi = 0, 0, len(a) - 1
  3. while mid <= hi:
  4. if a[mid] == 0:
  5. a[lo], a[mid] = a[mid], a[lo]
  6. lo += 1; mid += 1
  7. elif a[mid] == 1:
  8. mid += 1
  9. else:
  10. a[mid], a[hi] = a[hi], a[mid]
  11. hi -= 1; mid += 1
  12. return a
  13. print(tray([1, 2, 0]))

Choose an answer, then open Show answer below to check it.

Show answer
  • Answer: line 11 hi -= 1; mid += 1

Line 11 advances mid after swapping with hi, so the value that came from the right end is never inspected. Here a 0 swapped in from the end gets skipped.

30-second answer

Keep three regions with pointers: low (end of 0s), mid (scanner) and high (start of 2s). A 0 at mid swaps to low and both advance; a 1 just advances mid; a 2 swaps to high and only high moves, because the item swapped in has not been checked yet. One pass, O(n) time, O(1) space.

Practise saying it · 60 s. No recording, just a timer

Explain the three-pointer, one-pass colour sort.

Say your answer out loud, then check which of these points you covered:

  • Three regions and the invariant
  • Do not advance mid after a high swap
  • O(n), O(1)

Deep dive

Invariant: [0, low) are 0s, [low, mid) are 1s, (high, end] are 2s, [mid, high] is unknown.

Not advancing mid after swapping with high is the classic bug fix: the incoming value could be a 0.

Counting each colour and rewriting is two passes and also O(n); it is a fine baseline.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def sort_tray(tray: list[int]) -> list[int]:
    low, mid, high = 0, 0, len(tray) - 1
    while mid <= high:
        if tray[mid] == 0:
            tray[low], tray[mid] = tray[mid], tray[low]
            low += 1
            mid += 1
        elif tray[mid] == 1:
            mid += 1
        else:
            tray[mid], tray[high] = tray[high], tray[mid]
            high -= 1
    return tray

Common mistakes

  • Advancing mid after a swap with high.
  • Using mid < high instead of mid <= high, which leaves the last unknown item unchecked.

Senior take & follow-ups

Write the invariant before the code. With it, each branch is easy to justify.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about k colours?

    Show hint

    Counting sort in two passes, O(n + k).

  2. Where else does this partition appear?

    Show hint

    Three-way partitioning in quicksort, which handles many equal keys well.

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.