0704MediumArrayUnion-FindSorting

Smallest Reachable Pressure Row

Tracked in this browser only

Trains the technique from

LeetCode 2948Make Lexicographically Smallest Array by Swapping Elements

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

Python

def smallest_reachable_pressures(psi: list[int], limit: int) -> list[int]:

Java

public int[] smallestReachablePressures(int[] psi, int limit)

The intended approach

Time O(n log n) for n slots: one sort by pressure, plus per-run sorting of slot numbers totalling n entries.Space O(n) for the pressure ordering and the returned row.

A single exchange links two cylinders whose pressures are close, and repeated exchanges let a cylinder travel along a chain of such links, so the cylinders split into families that can be rearranged freely among the slots those cylinders occupy. Reading the slots in ascending pressure makes a family a contiguous run: a run ends exactly where the step from one pressure to the next exceeds `limit`. For each run, collect its slot numbers, sort them, and place the run's pressures into them in ascending order, which puts the smallest available pressure in the earliest slot the family owns.

Pythonentry point: smallest_reachable_pressures

def smallest_reachable_pressures(psi, limit):
    # O(n log n): read the slots in order of pressure, cut the reading wherever
    # two neighbouring pressures are more than `limit` apart, and inside each
    # piece hand the ascending pressures to the ascending slot numbers.
    n = len(psi)
    by_psi = sorted(range(n), key=lambda i: psi[i])
    out = [0] * n
    start = 0
    while start < n:
        end = start + 1
        while end < n and psi[by_psi[end]] - psi[by_psi[end - 1]] <= limit:
            end += 1
        slots = sorted(by_psi[start:end])
        for k, slot in enumerate(slots):
            out[slot] = psi[by_psi[start + k]]
        start = end
    return out

The obvious version

Breadth-first search over whole rows: from each row, apply every exchange the pressure limit allows and keep the smallest row ever seen. Explores the full reachable set, so it assumes nothing about which cylinders can travel together, and is only usable on very short rows.

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_smallest_reachable_pressures(psi, limit):
    start = tuple(psi)
    n = len(start)
    seen = {start}
    frontier = [start]
    best = start
    while frontier:
        nxt = []
        for cur in frontier:
            for i in range(n):
                for j in range(i + 1, n):
                    if abs(cur[i] - cur[j]) <= limit:
                        row = list(cur)
                        row[i], row[j] = row[j], row[i]
                        cand = tuple(row)
                        if cand not in seen:
                            seen.add(cand)
                            nxt.append(cand)
                            if cand < best:
                                best = cand
        frontier = nxt
    return list(best)

How this problem was checked

Reference solution executed against 17 test cases — 17 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