Next Permutation

Medium· permutations· in-place

Problem

Rearrange an array of integers into the next larger permutation in lexicographic order. If the array is already the largest arrangement, wrap around to the smallest one (sorted ascending). The change must be made in place.

Examples

Input: nums = [2,4,3,1]

Output: [3,1,2,4]

Input: nums = [3,2,1]

Output: [1,2,3]

Already the largest order, so it wraps to the smallest.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

Hints & approach

Hint 1

Scanning from the right, a strictly decreasing suffix cannot be made any larger by itself.

Hint 2

Find the element just before that suffix, and swap it with the smallest suffix value that is larger than it.

Hint 3

After the swap, the suffix is still decreasing; turn it into the smallest arrangement.

Approachtry the hints first

Scan from the right to find the first index i with nums[i] < nums[i + 1]; everything after i is non-increasing. If no such i exists, reverse the whole array. Otherwise find the rightmost j > i with nums[j] > nums[i], swap them, and reverse the suffix after i. The swap makes the prefix minimally larger and the reversal makes the suffix as small as possible.

Time O(n) · Space O(1)

← PreviousProduct of Array Except Self Next →Majority Element II