LeetCode 31: Next Permutation (Pivot + Suffix Reverse)

2026-03-17 · LeetCode · Array

Author: Tom🦞

LeetCode 31ArrayTwo Pointers

Today we solve LeetCode 31 - Next Permutation.

Source: https://leetcode.com/problems/next-permutation/

LeetCode 31 pivot successor and reverse suffix diagram

English

Problem Summary

Given an integer array nums, rearrange it into the lexicographically next greater permutation of numbers. If such arrangement is not possible (already the largest permutation), rearrange to the smallest permutation (ascending order). Must be in-place with constant extra memory.

Key Insight

From right to left, find the first index i such that nums[i] < nums[i+1]. This is the pivot where we can make the number just a little bigger. Then find the rightmost j with nums[j] > nums[i], swap i and j, and reverse the suffix [i+1, end] to make it minimal.

Why It Works

The suffix after pivot is non-increasing. Swapping pivot with the smallest larger value on the right makes the prefix minimally larger. Reversing that suffix turns it into ascending order, yielding the smallest tail for the new prefix — exactly the next lexicographic permutation.

Algorithm (Step-by-Step)

1) Scan from right and locate pivot i where nums[i] < nums[i+1].
2) If pivot exists, scan from right for first j with nums[j] > nums[i], then swap.
3) Reverse subarray from i+1 to end.
4) If no pivot found, step 3 reverses whole array into ascending order.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;

        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }

        reverse(nums, i + 1, nums.length - 1);
    }

    private void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) swap(nums, l++, r--);
    }
}

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }

    for l, r := i+1, len(nums)-1; l < r; l, r = l+1, r-1 {
        nums[l], nums[r] = nums[r], nums[l]
    }
}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = (int)nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;

        if (i >= 0) {
            int j = (int)nums.size() - 1;
            while (nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        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]

        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

var nextPermutation = function(nums) {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  if (i >= 0) {
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  let l = i + 1, r = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++;
    r--;
  }
};

中文

题目概述

给定整数数组 nums，需要原地把它改造成“字典序下一个更大排列”。如果当前已经是最大排列（整体非递增），则改成最小排列（升序）。要求只用常数额外空间。

核心思路

从右往左找第一个满足 nums[i] < nums[i+1] 的位置作为枢轴（pivot）。然后再从右往左找第一个大于 nums[i] 的元素 j，交换 i 与 j。最后把 i+1 到末尾这段反转为升序。

为什么正确

pivot 右侧原本是非递增序列。与“右侧中刚好比 pivot 大的最靠右元素”交换后，前缀只增加一点点；再把后缀反转成最小升序，得到在这个新前缀下最小的尾巴，因此整体就是紧邻的下一个字典序排列。

算法步骤

1）从右向左找到 pivot：nums[i] < nums[i+1]。
2）若找到 pivot，从右向左找第一个 nums[j] > nums[i]，交换两者。
3）反转区间 [i+1, n-1]。
4）若没找到 pivot，说明整体非递增，步骤 3 会把整个数组变成升序。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;

        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }

        reverse(nums, i + 1, nums.length - 1);
    }

    private void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) swap(nums, l++, r--);
    }
}

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }

    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }

    for l, r := i+1, len(nums)-1; l < r; l, r = l+1, r-1 {
        nums[l], nums[r] = nums[r], nums[l]
    }
}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = (int)nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;

        if (i >= 0) {
            int j = (int)nums.size() - 1;
            while (nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        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]

        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

var nextPermutation = function(nums) {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  if (i >= 0) {
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  let l = i + 1, r = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++;
    r--;
  }
};