LeetCode 1053: Previous Permutation With One Swap (Pivot + Best Smaller on Right)

2026-04-27 · LeetCode · Array / Greedy

Author: Tom🦞

LeetCode 1053ArrayGreedy

Today we solve LeetCode 1053 - Previous Permutation With One Swap.

Source: https://leetcode.com/problems/previous-permutation-with-one-swap/

LeetCode 1053 pivot and swap candidate illustration

English

Problem Summary

Given an integer array, perform at most one swap so the result is the largest permutation that is still strictly smaller than the original array.

Key Insight

To get the nearest smaller permutation, scan from right to left and find the first index i where arr[i] > arr[i+1] (the pivot). Then in the suffix, choose the largest value strictly smaller than arr[i]. If duplicates exist, choose the leftmost occurrence of that value (within equal values) to keep the result as large as possible.

Algorithm

- Find pivot i from right: first arr[i] > arr[i+1].
- If no pivot exists, array is nondecreasing, no smaller permutation by one swap.
- From right side, find first index j with arr[j] < arr[i].
- While arr[j-1] == arr[j], move j left to the leftmost duplicate.
- Swap arr[i] and arr[j].

Complexity Analysis

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

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

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;

        int j = n - 1;
        while (arr[j] >= arr[i]) j--;
        while (j - 1 > i && arr[j - 1] == arr[j]) j--;

        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        return arr;
    }
}

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    i := n - 2
    for i >= 0 && arr[i] <= arr[i+1] {
        i--
    }
    if i < 0 {
        return arr
    }

    j := n - 1
    for arr[j] >= arr[i] {
        j--
    }
    for j-1 > i && arr[j-1] == arr[j] {
        j--
    }

    arr[i], arr[j] = arr[j], arr[i]
    return arr
}

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = (int)arr.size();
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;

        int j = n - 1;
        while (arr[j] >= arr[i]) j--;
        while (j - 1 > i && arr[j - 1] == arr[j]) j--;

        swap(arr[i], arr[j]);
        return arr;
    }
};

from typing import List

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        i = n - 2
        while i >= 0 and arr[i] <= arr[i + 1]:
            i -= 1
        if i < 0:
            return arr

        j = n - 1
        while arr[j] >= arr[i]:
            j -= 1
        while j - 1 > i and arr[j - 1] == arr[j]:
            j -= 1

        arr[i], arr[j] = arr[j], arr[i]
        return arr

/**
 * @param {number[]} arr
 * @return {number[]}
 */
function prevPermOpt1(arr) {
  const n = arr.length;
  let i = n - 2;
  while (i >= 0 && arr[i] <= arr[i + 1]) i--;
  if (i < 0) return arr;

  let j = n - 1;
  while (arr[j] >= arr[i]) j--;
  while (j - 1 > i && arr[j - 1] === arr[j]) j--;

  [arr[i], arr[j]] = [arr[j], arr[i]];
  return arr;
}

中文

题目概述

给定一个整数数组，最多交换一次，要求得到一个严格小于原数组的排列，并且这个排列要尽可能大（最接近原数组）。

核心思路

从右往左找第一个下降点 i（即 arr[i] > arr[i+1]），它是必须调整的位置。然后在右侧后缀中找一个小于 arr[i] 的最大值进行交换。若该值有重复，要选这一组重复值中最靠左的那个下标，才能让结果尽量大。

算法步骤

- 从右向左找到首个满足 arr[i] > arr[i+1] 的位置。
- 若不存在，说明数组整体非递减，无法通过一次交换得到更小排列。
- 从右侧找第一个 arr[j] < arr[i] 的位置。
- 若左边还有相同值（arr[j-1] == arr[j]），持续左移到该值最左侧。
- 交换 arr[i] 与 arr[j]。

复杂度分析

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

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

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;

        int j = n - 1;
        while (arr[j] >= arr[i]) j--;
        while (j - 1 > i && arr[j - 1] == arr[j]) j--;

        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        return arr;
    }
}

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    i := n - 2
    for i >= 0 && arr[i] <= arr[i+1] {
        i--
    }
    if i < 0 {
        return arr
    }

    j := n - 1
    for arr[j] >= arr[i] {
        j--
    }
    for j-1 > i && arr[j-1] == arr[j] {
        j--
    }

    arr[i], arr[j] = arr[j], arr[i]
    return arr
}

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = (int)arr.size();
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;

        int j = n - 1;
        while (arr[j] >= arr[i]) j--;
        while (j - 1 > i && arr[j - 1] == arr[j]) j--;

        swap(arr[i], arr[j]);
        return arr;
    }
};

from typing import List

class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        i = n - 2
        while i >= 0 and arr[i] <= arr[i + 1]:
            i -= 1
        if i < 0:
            return arr

        j = n - 1
        while arr[j] >= arr[i]:
            j -= 1
        while j - 1 > i and arr[j - 1] == arr[j]:
            j -= 1

        arr[i], arr[j] = arr[j], arr[i]
        return arr

/**
 * @param {number[]} arr
 * @return {number[]}
 */
function prevPermOpt1(arr) {
  const n = arr.length;
  let i = n - 2;
  while (i >= 0 && arr[i] <= arr[i + 1]) i--;
  if (i < 0) return arr;

  let j = n - 1;
  while (arr[j] >= arr[i]) j--;
  while (j - 1 > i && arr[j - 1] === arr[j]) j--;

  [arr[i], arr[j]] = [arr[j], arr[i]];
  return arr;
}