0053MediumArrayTwo PointersSortingQuicksortBubble Sort

Triage Band Ordering

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def order_bands(bands: list[int]) -> list[int]:

Java

public int[] orderBands(int[] bands)

The intended approach

Time O(n)Space O(1)

Carry three markers: `low` is the first slot not yet claimed by an immediate band, `high` is the last slot not yet claimed by a routine band, and `mid` is the slot under inspection. An immediate code swaps down to `low` and both `low` and `mid` step forward, an urgent code is already where it belongs so only `mid` steps forward, and a routine code swaps up to `high`, which retreats while `mid` stays put because the value that arrived from the far end has not been inspected yet. The sweep ends once `mid` passes `high`.

Pythonentry point: order_bands

def order_bands(bands):
    low, mid, high = 0, 0, len(bands) - 1
    while mid <= high:
        code = bands[mid]
        if code == 0:
            bands[low], bands[mid] = bands[mid], bands[low]
            low += 1
            mid += 1
        elif code == 1:
            mid += 1
        else:
            bands[mid], bands[high] = bands[high], bands[mid]
            high -= 1
    return bands

The obvious version

Tally how many patients hold each of the three codes, then write out that many copies of each code in ascending order. Two passes and an auxiliary tally, which the statement forbids, but it is plainly correct.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_order_bands(bands):
    tally = [0, 0, 0]
    for code in bands:
        tally[code] += 1
    out = []
    for code in (0, 1, 2):
        out.extend([code] * tally[code])
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in