Next Permutation
Real-world version: Next Shelf ArrangementThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def next_arrangement(plates: list[int]) -> list[int]:public int[] nextArrangement(int[] plates)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's