Next Permutation
Medium · rating 1500 · Arrays
The first line has n. The second line has a permutation of n integers. Print the next lexicographically greater permutation, or the smallest one (sorted ascending) if the input is the largest.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Scan from the right for the first index i where a[i] < a[i+1] — the pivot. Everything to its right is descending (already the largest arrangement). Swap the pivot with the smallest element to its right that still exceeds it, then reverse the suffix to make it ascending (the smallest continuation).
Why this is the very next one
Increasing the pivot as little as possible, then minimising everything after it, yields the immediately larger permutation. If no pivot exists the array was the largest, so we reverse the whole thing to the smallest.
i = n-2
while i >= 0 and a[i] >= a[i+1]: i -= 1
if i >= 0:
j = n-1
while a[j] <= a[i]: j -= 1
a[i], a[j] = a[j], a[i]
a[i+1:] = reversed(a[i+1:])Complexity
Time: O(n). Space: O(1).
Related problems
- Minimum in Rotated Array — Medium
- Next Greater Element — Medium
- Product of Array Except Self — Hard
- Search in Rotated Array — Medium
- Count Pairs With Difference — Medium
- Count Pairs with Sum — Medium