0052MediumArrayTwo Pointers

Next Shelf Arrangement

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 display shelf carries one numbered price plate per slot, given left to right as the integer array plates. Head office ranks every possible left-to-right reading of this exact multiset of plates, comparing two readings position by position and putting the one with the smaller number at the first position where they differ ahead of the other.

Every morning the shelf has to move to whichever reading sits immediately after the current reading in that ranking. If the current reading is already the very last one, the shelf wraps around to the first reading in the ranking, which is the plates arranged in non-decreasing order.

Rearrange plates itself. You may hold a fixed number of extra variables and nothing that grows with the number of slots, so no second array and no list of candidate readings. Return plates after rearranging it.

Examples

Example 1

Input: plates = [2, 5, 4]
Output: [4, 2, 5]

Ranked, the readings of these three plates run 2 4 5, then 2 5 4, then 4 2 5, and so on. The shelf currently shows the second of those, so it moves to the third.

Example 2

Input: plates = [7, 6, 3]
Output: [3, 6, 7]

No reading of these plates ranks above 7 6 3, so the shelf wraps back to the lowest ranked reading.

Example 3

Input: plates = [1, 5, 5, 2]
Output: [2, 1, 5, 5]

The 1 in slot 0 is the last plate that has a larger plate somewhere to its right. Trading it with the smallest such plate, the 2, and then laying the remaining tail out in non-decreasing order gives the next reading up.

Constraints

1 <= plates.length <= 100
0 <= plates[i] <= 100
Only a constant amount of extra space may be used
`plates` 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 next_arrangement(plates: list[int]) -> list[int]:

Java

public int[] nextArrangement(int[] plates)

The intended approach

Time O(n)Space O(1)

Scan from the right for the last slot `i` whose plate is strictly below the plate just after it; everything to the right of `i` is already non-increasing, so it is the top ranked tail and cannot be advanced on its own. Trade the plate at `i` with the rightmost plate in that tail that still exceeds it, which is the smallest available step up, then reverse the tail so it becomes the lowest ranked layout. If no such `i` exists the whole shelf is non-increasing, and reversing it from position 0 produces the wrap-around reading.

Pythonentry point: next_arrangement

def next_arrangement(plates):
    n = len(plates)
    i = n - 2
    while i >= 0 and plates[i] >= plates[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while plates[j] <= plates[i]:
            j -= 1
        plates[i], plates[j] = plates[j], plates[i]
    left, right = i + 1, n - 1
    while left < right:
        plates[left], plates[right] = plates[right], plates[left]
        left += 1
        right -= 1
    return plates

The obvious version

Materialise every distinct reading of the multiset, sort them, locate the current one and step to the following entry with wrap-around. Factorial time and memory, but it follows the definition literally.

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_next_arrangement(plates):
    from itertools import permutations
    current = tuple(plates)
    ranked = sorted(set(permutations(current)))
    pos = ranked.index(current)
    return list(ranked[(pos + 1) % len(ranked)])

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