Next Permutation

Medium

Problem

Rearrange the array into the next lexicographically larger permutation of its values. If it is already the largest permutation, rearrange it into the smallest (sorted ascending). Do it in place with O(1) extra space.

Example 1

Input:  [1, 2, 3]
Output: [1, 3, 2]

Example 2

Input:  [3, 2, 1]
Output: [1, 2, 3]

Already the largest, so wrap around to the smallest.

Example 3

Input:  [1, 3, 2]
Output: [2, 1, 3]

Also asked as: Next Permutation

Test cases

Case 1

Input:    [1,2,3]
Expected: [1,3,2]

Case 2

Input:    [3,2,1]
Expected: [1,2,3]

Case 3

Input:    [1,3,2]
Expected: [2,1,3]

Case 4

Input:    [1,1,5]
Expected: [1,5,1]

Case 5

Input:    [1]
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Pivot, swap, reverse suffix

Time O(n)Space O(1)

Find the rightmost `i` with a[i] < a[i+1]. Swap a[i] with the rightmost element greater than it, then reverse the suffix after i.

function nextPermutation(a) {
let i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
let j = a.length - 1;
while (a[j] <= a[i]) j--;
[a[i], a[j]] = [a[j], a[i]];
}
// reverse suffix
let l = i + 1, r = a.length - 1;
while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
return a;
}