625. The Next Arrangement
Rearrange the given numbers into the next arrangement that is LARGER when the sequences are compared left to right. If the given arrangement is already the largest, print the smallest one instead, which is the values sorted increasingly.
1 2 3 -> 1 3 2
3 2 1 -> 1 2 3 already largest, so wrap to the smallest
1 1 5 -> 1 5 1
## Do not generate the arrangements
Listing every arrangement and picking the successor is O(n! * n). The answer is reachable in
one pass from the right, in O(n), and the reason is worth understanding rather than
memorising.
## Where the change must happen
Read from the right. A suffix that is non-increasing, such as 5 4 4 1, is already the
LARGEST arrangement of its own values, so nothing inside it can be improved. The change must
therefore happen at the first position, scanning right to left, whose value is smaller than
its right-hand neighbour. Call it the PIVOT.
i = n-2
while i >= 0 and a[i] >= a[i+1]: i -= 1
If no such position exists, the whole sequence is non-increasing and therefore the largest. The answer is then the smallest arrangement, which is the reverse of what we have.
## What replaces the pivot
To get the next larger sequence, the pivot must grow by the SMALLEST possible amount. So find the rightmost value in the suffix that is strictly greater than the pivot, and swap them:
j = n-1
while a[j] <= a[i]: j -= 1
swap a[i], a[j]
Scanning from the right finds the smallest such value, because the suffix is non-increasing. And the suffix stays non-increasing after the swap: the incoming value fits in the same slot the outgoing one occupied.
## Then make the tail as small as possible
The prefix is now correct and must not change. The suffix should be the smallest arrangement of its values, and since it is non-increasing, the smallest is simply its reverse:
reverse a[i+1 .. n-1]
That reversal is where the two pointers come in, converging from both ends of the suffix.
## Why the wrap-around needs no special case
When no pivot exists, the code reverses the WHOLE array, which is exactly the sorted-increasing order because the array was non-increasing. So one line covers both the ordinary case and the wrap.
## Boundaries
A single value prints itself. All values equal prints them unchanged, because it is simultaneously largest and smallest.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print the n values of the next arrangement on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.