Rearrange the integer array nums into the next arrangement that is larger in dictionary (lexicographic) order. If nums is already the largest arrangement, rearrange it into the smallest one (sorted ascending). Do it in place with O(1) extra memory.
[1,2,3] is [1,3,2].- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Generating all permutations, sorting them and picking the next one is O(n!), hopeless. Instead, notice that a decreasing suffix cannot be made any larger by rearranging it. So find the rightmost index i with nums[i] < nums[i+1]: this is the digit we must bump up. Swap it with the smallest larger value in the suffix (the rightmost one bigger than it), and then make the suffix as small as possible. Since the suffix is still decreasing, reversing it sorts it ascending.
Algorithm
- Find the largest
iwithnums[i] < nums[i+1]. If none exists, reverse the whole array and stop. - Find the largest
j > iwithnums[j] > nums[i]. - Swap
nums[i]andnums[j]. - Reverse the part from
i + 1to the end.
O(n)Space: O(1)nums[i] < nums[i+1] and nums[j] > nums[i]. Using <= or >= breaks inputs like [1,5,1] or [1,1,5].class Solution: def nextPermutation(self, nums: List[int]) -> None: n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 # find the pivot if i >= 0: j = n - 1 while nums[j] <= nums[i]: j -= 1 # rightmost value bigger than the pivot nums[i], nums[j] = nums[j], nums[i] # the suffix is decreasing: reverse it to make it as small as possible l, r = i + 1, n - 1 while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1