Previous Permutation With One Swap

Medium
1130.

Previous Permutation With One Swap

Previous Permutation With One Swap is a medium coding problem on arrays and greedy, asked in Amazon and Meta interviews.

You are given an array of positive integers arr (values may repeat).

A swap exchanges the values at two positions i and j. Among all arrays obtainable from arr with exactly one swap that are lexicographically smaller than arr, return the lexicographically largest one.

If no single swap makes arr smaller, return arr unchanged.

Example 1

Input
arr = [4,3,2]
Output
[4,2,3]
Explanation
Swapping the last two values gives the largest array that is still smaller.

Example 2

Input
arr = [2,2,7]
Output
[2,2,7]
Explanation
The array is non-decreasing, so every swap makes it larger or leaves it equal.

Example 3

Input
arr = [4,1,1,4]
Output
[1,4,1,4]
Explanation
Swapping 4 with the *first* of the two 1s keeps the larger value as far left as possible.

Constraints

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Previous Permutation With One Swap — Problem & Solution

Previous Permutation With One Swap solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Previous Permutation With One Swap is a medium coding problem on arrays and greedy, asked in Amazon and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array of positive integers arr (values may repeat).

A swap exchanges the values at two positions i and j. Among all arrays obtainable from arr with exactly one swap that are lexicographically smaller than arr, return the lexicographically largest one.

If no single swap makes arr smaller, return arr unchanged.

Example 1

Input: arr = [4,3,2]
Output: [4,2,3]
Explanation: Swapping the last two values gives the largest array that is still smaller.

Example 2

Input: arr = [2,2,7]
Output: [2,2,7]
Explanation: The array is non-decreasing, so every swap makes it larger or leaves it equal.

Example 3

Input: arr = [4,1,1,4]
Output: [1,4,1,4]
Explanation: Swapping 4 with the *first* of the two 1s keeps the larger value as far left as possible.

Constraints

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

Hints for Previous Permutation With One Swap

  1. Hint 1

    To make the array smaller but as large as possible, change it as far to the right as you can.

  2. Hint 2

    The leftmost changed position must receive a smaller value from its right. Find the rightmost i with arr[i] > arr[i + 1].

  3. Hint 3

    Swap arr[i] with the largest value to its right that is still smaller than arr[i]; if that value occurs several times, take its leftmost occurrence.

How to solve Previous Permutation With One Swap

The swap should touch the latest possible position i (so the shared prefix is as long as possible) and put there the largest smaller value available to its right.

Approach

  1. Scan from the right for the first index i with arr[i] > arr[i + 1]. If none exists, the array is non-decreasing — return it.
  2. Among indices j > i, the values smaller than arr[i] are candidates. Pick the largest such value.
  3. If that value appears several times, choose the leftmost of its occurrences after i.
  4. Swap arr[i] and arr[j] and return the array.

Why it works

A smaller result must lower the first position it changes, and that position needs a smaller value somewhere to its right — the rightmost such position is i, and everything after i is non-decreasing. Putting the largest smaller value at i maximises position i. The displaced arr[i] lands at j; among equal candidates the leftmost j places the larger value arr[i] earliest, which maximises the rest.

Complexity

  • Time — O(n)
  • Space — O(1) (plus the output copy)

Pitfalls

  • Picking the rightmost duplicate of the chosen value gives a smaller result: [4,1,1,4] must become [1,4,1,4], not [1,1,4,4].
  • Because the suffix after i is non-decreasing, scanning j leftwards from the end while arr[j] >= arr[i] finds the largest smaller value.
  • An already non-decreasing array has no smaller neighbour — return it as is.

Reference solution

Python

from typing import List

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

Java

public static int[] prevPermOpt1(int[] arr) {
    int[] a = arr.clone();
    int n = a.length;
    int i = n - 2;
    while (i >= 0 && a[i] <= a[i + 1]) i--;
    if (i < 0) return a;
    int j = n - 1;
    while (a[j] >= a[i]) j--;
    while (j - 1 > i && a[j - 1] == a[j]) j--;
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
    return a;
}

C++

vector<int> prevPermOpt1(vector<int>& arr) {
    vector<int> a(arr);
    int n = a.size();
    int i = n - 2;
    while (i >= 0 && a[i] <= a[i + 1]) i--;
    if (i < 0) return a;
    int j = n - 1;
    while (a[j] >= a[i]) j--;
    while (j - 1 > i && a[j - 1] == a[j]) j--;
    swap(a[i], a[j]);
    return a;
}

JavaScript

var prevPermOpt1 = function(arr) {
    var a = arr.slice();
    var n = a.length;
    var i = n - 2;
    while (i >= 0 && a[i] <= a[i + 1]) i--;
    if (i < 0) return a;
    var j = n - 1;
    while (a[j] >= a[i]) j--;
    while (j - 1 > i && a[j - 1] === a[j]) j--;
    var t = a[i];
    a[i] = a[j];
    a[j] = t;
    return a;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms