Next Permutation
The key idea
Scan from the right for the first index
i where nums[i] < nums[i+1] — this is the pivot, the last spot that can be increased. The suffix after it is non-increasing (already the largest it can be). Swap nums[i] with the smallest element to its right that is still larger than it, then reverse the suffix so it becomes ascending (the smallest tail). If no pivot exists the whole array is descending, so reverse it all.Problem
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
The next permutation of an array of integers is the next lexicographically greater permutation of its integers. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
Given an array of integers nums, rearrange nums into its next permutation.
The replacement must be in place and use only constant extra memory.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 100
Examples
Input: nums = [1,2,3]
Output: [1,3,2]
Input: nums = [3,2,1]
Output: [1,2,3]
Input: nums = [1,1,5]
Output: [1,5,1]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY
- Reverse StringEASY