Show problems as
Classic problem #2161MediumArrayTwo PointersSimulation

Partition Array According to Given Pivot

Real-world version: Reorder Readings Around a Reference
Tracked in this browser only
Read Partition Array According to Given Pivot on LeetCode(opens in a new tab)

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

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

Python
def reorder_readings(readings: list[int], reference: int) -> list[int]:
Java
public int[] reorderReadings(int[] readings, int reference)

More on the same topics