Next Permutation: Pivot and Suffix Reversal Pattern

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.

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 end
  

Reference 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

Complexity

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

The suffix is descending, so reversing it gives the smallest possible order after making the prefix larger.

The array is the largest permutation, so reversing the full array returns the smallest permutation.

Lexicographic pivot plus suffix reversal.