0682MediumArrayTwo PointersSimulation

Reorder Readings Around a Reference

Tracked in this browser only

Trains the technique from

LeetCode 2161Partition Array According to Given Pivot

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 calibration run leaves you with a list of signed drift readings, one per probe, in the order the probes were sampled. One of the sampled values is singled out as the reference.

Rearrange the readings into a new list so that:

every reading smaller than reference comes before every reading equal to reference;
every reading equal to reference comes before every reading larger than reference;
two readings that are both smaller than reference keep the order they had in the input, and two readings that are both larger than reference also keep the order they had in the input.

Return the rearranged list. Exactly one list satisfies all three rules, so the answer is unique.

Examples

Example 1

Input: readings = [8, 2, 7, 5, 1, 5], reference = 5
Output: [2, 1, 5, 5, 8, 7]

The readings smaller than `5` are `2` and `1`, read in that order, and they open the list. The two readings equal to `5` follow. The readings larger than `5` are `8` and `7`, read in that order, and they close the list.

Example 2

Input: readings = [-5, 2, -9, 2], reference = 2
Output: [-5, -9, 2, 2]

Nothing is larger than `2`, so the list is just the two smaller readings `-5` and `-9` in their sampled order, followed by the two readings equal to `2`.

Example 3

Input: readings = [0, -4, 6, -4, 6, 0, -4], reference = -4
Output: [-4, -4, -4, 0, 6, 6, 0]

No reading is smaller than `-4`, so the three readings equal to `-4` come first. The four larger readings keep their sampled order `0`, `6`, `6`, `0`.

Constraints

1 <= readings.length <= 10^5
-10^6 <= readings[i] <= 10^6
-10^6 <= reference <= 10^6
reference is equal to at least one of the readings.

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 reorder_readings(readings: list[int], reference: int) -> list[int]:

Java

public int[] reorderReadings(int[] readings, int reference)

The intended approach

Time O(n) for n readings: two walks over the input, no sorting.Space O(n) for the returned list, O(1) besides it.

Count how many readings fall below the reference and how many equal it. Those two counts fix where each of the three blocks starts in the output, so a second walk over the input can drop every reading straight into its final slot with a write cursor per block. Because each block's cursor only ever moves forward, readings that share a block come out in the order they were read.

Pythonentry point: reorder_readings

def reorder_readings(readings, reference):
    # first pass: how many readings fall in each of the three groups, which fixes
    # the block boundaries in the output
    below = 0
    same = 0
    for v in readings:
        if v < reference:
            below += 1
        elif v == reference:
            same += 1
    out = [0] * len(readings)      # O(n) for the returned list
    lo = 0
    mid = below
    hi = below + same
    # second pass: every reading goes straight to its final slot, so the order
    # inside each block is the order it was read in
    for v in readings:
        if v < reference:
            out[lo] = v
            lo += 1
        elif v == reference:
            out[mid] = v
            mid += 1
        else:
            out[hi] = v
            hi += 1
    return out

The obvious version

Label each reading 0, 1 or 2 depending on how it compares with the reference, then run a plain insertion sort that only ever swaps a larger label in front of a smaller one. Insertion sort never swaps equal labels, so readings sharing a label stay in their original order. Quadratic, but it makes no assumption about block sizes.

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_reorder_readings(readings, reference):
    def group(v):
        if v < reference:
            return 0
        if v == reference:
            return 1
        return 2

    out = list(readings)
    for i in range(1, len(out)):
        j = i
        while j > 0 and group(out[j - 1]) > group(out[j]):
            out[j - 1], out[j] = out[j], out[j - 1]
            j -= 1
    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