Next Arrangement
MediumTwo Pointers
Problem
A seating planner lists every arrangement of the values in nums in lexicographic (dictionary) order. Rearrange nums in place into the arrangement that comes right after the current one.
If the current arrangement is the last one, wrap around to the first: the values in non-decreasing order. Use O(1) extra memory.
Example 1
- Input:
- nums = [1, 3, 2]
- Output:
- [2, 1, 3]
In order: [1,2,3], [1,3,2], [2,1,3], … so [2, 1, 3] follows.
Example 2
- Input:
- nums = [3, 2, 1]
- Output:
- [1, 2, 3]
The last arrangement wraps to the first.
Example 3
- Input:
- nums = [1, 1, 5]
- Output:
- [1, 5, 1]
Constraints
- 1 ≤ nums.length ≤ 10^5
- 0 ≤ nums[i] ≤ 100
Hint
Show the first hint
The longest non-increasing suffix is already at its largest possible order. What must change just before it?
Walkthrough
How to approach it
01Clarify before coding
- Can values repeat? Yes; the next arrangement is among distinct arrangements.
- What if nums is the largest arrangement? Wrap to the smallest (sorted ascending).
- Must it be in place? Yes, the function returns nothing.
02Brute force
Generate all arrangements in sorted order and pick the one after the current.
Cost: O(n!·n): impossible beyond about 10 elements.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.