Next Permutation
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]
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;}