Problem

Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap. If it cannot be done, then return the same array.

Note that a swap exchanges the positions of two numbers arr[i] and arr[j]

Examples

Example 1

1
2
3

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2

1
2
3

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3

1
2
3

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Constraints

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^4

Solution

Intuition

To get the previous permutation with one swap, we want the largest permutation smaller than the current one. We scan from right to left to find the first index i where arr[i] > arr[i+1]. Then, we swap arr[i] with the largest value to its right that is less than arr[i] (and as rightmost as possible for duplicates).

Approach

  1. Traverse from right to left, find the first i where arr[i] > arr[i+1].
  2. If not found, return arr (already smallest).
  3. From the end, find the largest j > i such that arr[j] < arr[i] and arr[j] != arr[j-1] (to avoid duplicate swaps).
  4. Swap arr[i] and arr[j].
  5. Return arr.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
using namespace std;
vector<int> prevPermOpt1(vector<int>& arr) {
    int n = arr.size();
    for (int i = n-2; i >= 0; --i) {
        if (arr[i] > arr[i+1]) {
            int j = n-1;
            while (arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j-1])) --j;
            swap(arr[i], arr[j]);
            break;
        }
    }
    return arr;
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    for i := n-2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            j := n-1
            for j > 0 && (arr[j] >= arr[i] || arr[j] == arr[j-1]) {
                j--
            }
            arr[i], arr[j] = arr[j], arr[i]
            break
        }
    }
    return arr
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n-2; i >= 0; --i) {
            if (arr[i] > arr[i+1]) {
                int j = n-1;
                while (arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j-1])) --j;
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
                break;
            }
        }
        return arr;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fun prevPermOpt1(arr: IntArray): IntArray {
    val n = arr.size
    for (i in n-2 downTo 0) {
        if (arr[i] > arr[i+1]) {
            var j = n-1
            while (j > 0 && (arr[j] >= arr[i] || arr[j] == arr[j-1])) j--
            val tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp
            break
        }
    }
    return arr
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List
def prevPermOpt1(arr: List[int]) -> List[int]:
    n = len(arr)
    for i in range(n-2, -1, -1):
        if arr[i] > arr[i+1]:
            j = n-1
            while arr[j] >= arr[i] or (j > 0 and arr[j] == arr[j-1]):
                j -= 1
            arr[i], arr[j] = arr[j], arr[i]
            break
    return arr
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

fn prev_perm_opt1(arr: &mut Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    for i in (0..n-1).rev() {
        if arr[i] > arr[i+1] {
            let mut j = n-1;
            while arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j-1]) {
                j -= 1;
            }
            arr.swap(i, j);
            break;
        }
    }
    arr.clone()
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

export function prevPermOpt1(arr: number[]): number[] {
    const n = arr.length;
    for (let i = n-2; i >= 0; --i) {
        if (arr[i] > arr[i+1]) {
            let j = n-1;
            while (arr[j] >= arr[i] || (j > 0 && arr[j] === arr[j-1])) --j;
            [arr[i], arr[j]] = [arr[j], arr[i]];
            break;
        }
    }
    return arr;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)