Learning Outcome
After this lesson, you should be able to identify the rightmost pivot and rebuild the smallest larger suffix.
Problem Statement
Given an integer array, rearrange it into the next lexicographically greater permutation. If none exists, rearrange it into the lowest order.
| Input | Output | Why |
|---|---|---|
nums = [1,2,3] | [1,3,2] | The next arrangement after 1,2,3 is 1,3,2. |
Brute Force Approach
Generate all permutations, sort them, and select the next one. This is factorial time.
Optimized Approach
Find the rightmost index i where nums[i] < nums[i + 1]. Swap it with the smallest larger value in the suffix, then reverse the suffix.
Exact Pseudocode
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap nums[i], nums[j]
reverse nums from i + 1 to endReference Code
class Solution:
def nextPermutation(self, nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = reversed(nums[i + 1:])Sample Dry Run
| Step | State | Result |
|---|---|---|
| Find pivot | In [1,2,3], i = 1 because 2 < 3 | pivot is 2 |
| Find next larger | j = 2, value 3 | swap 2 and 3 |
| Reverse suffix | suffix after pivot is [2] | unchanged |
| Return | [1,3,2] | next permutation |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | At most three linear scans are performed. |
| Space | O(1) | The array is modified in-place. |
Edge Cases
- A fully descending array becomes ascending.
- Duplicates are allowed.
- Single-element arrays stay unchanged.
Interview Checklist
- Find the rightmost increasing pivot.
- Swap with the rightmost larger suffix value.
- Reverse only the suffix after the pivot.
FAQs
Why reverse the suffix?
The suffix is descending, so reversing it gives the smallest possible order after making the prefix larger.
What if no pivot exists?
The array is the largest permutation, so reversing the full array returns the smallest permutation.
What is the core pattern?
Lexicographic pivot plus suffix reversal.