Show problems as
Classic problem #2948MediumArrayUnion-FindSorting

Make Lexicographically Smallest Array by Swapping Elements

Real-world version: Smallest Reachable Pressure Row
Tracked in this browser only
Read Make Lexicographically Smallest Array by Swapping Elements on LeetCode(opens in a new tab)

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

A gas store has a row of numbered slots, each holding one cylinder. psi[i] is the pressure of the cylinder currently in slot i.

A handling rig can exchange the cylinders sitting in two slots, but only when their pressures differ by at most limit. The rig may carry out any number of exchanges, in any order, and an exchange never changes a cylinder's pressure.

Return the row of pressures, slot by slot, that is lexicographically smallest among all rows the rig can reach. Row a is lexicographically smaller than row b of the same length when at the first slot where they differ, a holds the smaller pressure.

Examples

Example 1

Input
psi = [9, 4, 2, 8, 5, 1], limit = 2
Output
[8, 1, 2, 9, 4, 5]

One reachable sequence of exchanges is: slots 0 and 3 (pressures 9 and 8) giving `[8, 4, 2, 9, 5, 1]`, then slots 1 and 2 (4 and 2) giving `[8, 2, 4, 9, 5, 1]`, then slots 1 and 5 (2 and 1) giving `[8, 1, 4, 9, 5, 2]`, then slots 2 and 5 (4 and 2) giving `[8, 1, 2, 9, 5, 4]`, then slots 4 and 5 (5 and 4) giving `[8, 1, 2, 9, 4, 5]`. Every exchange used two pressures at most 2 apart.

Example 2

Input
psi = [12, 3, 10, 1, 11, 2], limit = 1
Output
[10, 1, 11, 2, 12, 3]

Exchanging slots 0 and 4 (12 and 11) gives `[11, 3, 10, 1, 12, 2]`, then slots 0 and 2 (11 and 10) gives `[10, 3, 11, 1, 12, 2]`, then slots 1 and 5 (3 and 2) gives `[10, 2, 11, 1, 12, 3]`, then slots 1 and 3 (2 and 1) gives `[10, 1, 11, 2, 12, 3]`. Every exchange used two pressures 1 apart.

Example 3

Input
psi = [8, 2, 6, 4], limit = 1
Output
[8, 2, 6, 4]

No two of these four pressures differ by 1 or less, so the rig cannot make a single exchange and the row stays exactly as it started.

Constraints

  • 1 <= psi.length <= 10^5
  • 1 <= psi[i] <= 10^9
  • 1 <= limit <= 10^9

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 smallest_reachable_pressures(psi: list[int], limit: int) -> list[int]:
Java
public int[] smallestReachablePressures(int[] psi, int limit)

More on the same topics