Show problems as
Classic problem #75MediumArrayTwo PointersSortingQuicksortBubble Sort

Sort Colors

Real-world version: Triage Band Ordering
Tracked in this browser only
Read Sort Colors on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSorting · Arrays, animated step by step

A walk-in clinic gives every waiting patient a wrist band carrying one of three codes: 0 for immediate, 1 for urgent, 2 for routine. The array bands lists those codes in the order the patients arrived.

Rebuild the queue so that the codes climb: no immediate band may sit behind an urgent or routine band, and no urgent band may sit behind a routine band. Patients sharing a code are interchangeable, so their relative positions do not matter.

Work on bands itself and return it. Touch each position a bounded number of times in one sweep across the array, keep only a fixed set of extra variables, and do not hand the work to a sorting routine from your language's library.

Examples

Example 1

Input
bands = [1, 2, 0, 1, 2, 0]
Output
[0, 0, 1, 1, 2, 2]

Two patients hold an immediate band, two hold urgent and two hold routine, so the queue settles into those three runs.

Example 2

Input
bands = [2, 1, 0]
Output
[0, 1, 2]

The queue arrived in exactly the wrong order, so all three patients change position.

Example 3

Input
bands = [1, 1]
Output
[1, 1]

Both bands carry the same code, so the queue already climbs and nothing moves.

Constraints

  • n == bands.length
  • 1 <= n <= 300
  • bands[i] is either 0, 1, or 2
  • Only a constant amount of extra space may be used
  • `bands` must be rearranged in place and returned

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def order_bands(bands: list[int]) -> list[int]:
Java
public int[] orderBands(int[] bands)

More on the same topics