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^41 <= arr[i] <= 10^4
Hints for Previous Permutation With One Swap
Hint 1
To make the array smaller but as large as possible, change it as far to the right as you can.
Hint 2
The leftmost changed position must receive a smaller value from its right. Find the rightmost
iwitharr[i] > arr[i + 1].Hint 3
Swap
arr[i]with the largest value to its right that is still smaller thanarr[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
- Scan from the right for the first index
iwitharr[i] > arr[i + 1]. If none exists, the array is non-decreasing — return it. - Among indices
j > i, the values smaller thanarr[i]are candidates. Pick the largest such value. - If that value appears several times, choose the leftmost of its occurrences after
i. - Swap
arr[i]andarr[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
iis non-decreasing, scanningjleftwards from the end whilearr[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 aJava
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