Previous Permutation With One Swap solution and explanation
9 more videos on this problem
Facebook Coding Interview Question | Leetcode 1053 | Previous Permutation With One SwapWorkWithGoogler · 9:42 · 1K views
LeetCode 1053. Previous Permutation With One Swap | JSer - JavaScript & AlgorithmJSer · 10:32 · 916 views
【每日一题】1053. Previous Permutation With One Swap, 2/8/2020Huifeng Guan · 10:29 · 409 views
米开：LeetCode 1053. Previous Permutation With One SwapM.C米开朗基罗 · 9:56 · 360 views
Leetcode 1053. Previous Permutation With One Swap (next smaller)LetsCode · 11:18 · 110 views
猩猩的乐园 Leetcode 1053 Previous Permutation With One Swap猩猩的乐园 · 8:33 · 69 views
LeetCode 1053: Previous Permutation With One SwapAlitaCode · 27:30 · 26 views
LeetCode 1053: Previous Permutation With One SwapAlitaCode · 25:19 · 10 views
[Unscripted] LC1053 - Previous Permutation With One Swap | 01/11/2025career diaries · 41:23 · 10 views
No Sound Leetcode 1053: Previous Permutation with One SwapExtremeProgrammer · 2:12 · 8 views
The 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]
Example 1:
Input: arr = [3,2,1] Output: [3,1,2] Explanation: Swapping 2 and 1.
Example 2:
Input: arr = [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation.
Example 3:
Input: arr = [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swapping 9 and 7.
Constraints:
1 <= arr.length <= 1041 <= arr[i] <= 104
Approach overview
Problem Overview: You are given an integer array representing a permutation. The task is to produce the largest permutation that is strictly smaller than the current one using exactly one swap. If no such permutation exists, return the original array.
Approach 1: Brute Force Pair Swaps (O(n²) time, O(1) space)
The simplest idea is to try every possible pair of indices (i, j) where i < j. For each pair, swap the elements and check if the resulting array is lexicographically smaller than the original. Track the largest valid permutation among all candidates. This works because the array size is usually manageable, but it requires comparing many permutations and repeatedly swapping elements. The time complexity is O(n²) due to testing all pairs, while space remains O(1) since swaps are done in place. This approach demonstrates the permutation ordering idea but is rarely used in interviews.
Approach 2: Reverse Traversal for Optimal Swap (O(n) time, O(1) space)
The optimal strategy scans the array from right to left to locate the first index i where arr[i] > arr[i+1]. This position is the pivot where decreasing the permutation becomes possible. Once found, scan the suffix again to locate the largest value smaller than arr[i]. If duplicates exist, choose the leftmost occurrence of that value to avoid producing a smaller-than-necessary permutation. Swap these two elements and return the result. The algorithm performs a single reverse traversal plus a small suffix scan, resulting in O(n) time and O(1) space. This is the standard greedy solution based on permutation ordering and is closely related to the next-permutation pattern.
Approach 3: Optimal Swap Using Well-Placed Element (O(n) time, O(1) space)
This variation emphasizes selecting the best candidate from the suffix in a single controlled scan. After identifying the pivot index using reverse traversal, iterate through the suffix and track the best "well‑placed" element — the largest number strictly smaller than the pivot value. When duplicates appear, move leftward to ensure the swap keeps the permutation as large as possible. The core idea is still greedy: reduce the permutation minimally while maintaining maximum lexicographic order. Time complexity remains O(n) with O(1) extra space. This formulation is often easier to reason about during interviews.
Recommended for interviews: Interviewers expect the greedy reverse traversal solution. Starting with the brute-force swap idea shows understanding of permutation ordering, but identifying the pivot and choosing the best smaller element demonstrates strong greedy reasoning and efficient array traversal patterns commonly used in permutation problems.
Approach 1: Reverse Traversal for Optimal Swap
In this approach, the idea is to traverse the array from right to left to find the first pair of elements that violate the increasing trend. This identifies the point where a swap could potentially yield a smaller permutation. We then scan the remaining portion of the array to find the largest element that is smaller than the identified element, and swap them. This ensures we get the highest permutation possible that is smaller than the original array.
def prevPermOpt1(arr):
n = len(arr)
for i in range(n - 2, -1, -1):
if arr[i] > arr[i + 1]:
for j in range(n - 1, i, -1):
if arr[j] < arr[i] and arr[j] != arr[j - 1]:
arr[i], arr[j] = arr[j], arr[i]
return arr
return arr
arr = [1, 9, 4, 6, 7]
print(prevPermOpt1(arr))import java.util.Arrays;
class Solution {
public void prevPermOpt1(int[] arr) {
int n = arr.length, i, j;
for (i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
for (j = n - 1; j > i; j--) {
if (arr[j] < arr[i] && arr[j] != arr[j - 1]) {
swap(arr, i, j);
return;
}
}
}
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 9, 4, 6, 7};
sol.prevPermOpt1(arr);
System.out.println(Arrays.toString(arr));
}
}#include <vector>
#include <iostream>
#include <algorithm>
class Solution {
public:
void prevPermOpt1(std::vector<int>& arr) {
int n = arr.size(), i, j;
for (i = n - 2; i >= 0; --i) {
if (arr[i] > arr[i + 1]) {
for (j = n - 1; j > i; --j) {
if (arr[j] < arr[i] && arr[j] != arr[j - 1]) {
std::swap(arr[i], arr[j]);
return;
}
}
}
}
}
};
int main() {
std::vector<int> arr = {1, 9, 4, 6, 7};
Solution().prevPermOpt1(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}function prevPermOpt1(arr) {
let n = arr.length;
for (let i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
for (let j = n - 1; j > i; j--) {
if (arr[j] < arr[i] && arr[j] !== arr[j - 1]) {
[arr[i], arr[j]] = [arr[j], arr[i]];
return arr;
}
}
}
}
return arr;
}
console.log(prevPermOpt1([1, 9, 4, 6, 7]));#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void prevPermOpt1(int* arr, int arrSize){
int i, j;
for (i = arrSize - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
for (j = arrSize - 1; j > i; j--) {
if (arr[j] < arr[i] && arr[j] != arr[j - 1]) {
swap(&arr[i], &arr[j]);
return;
}
}
}
}
}
int main() {
int arr[] = {1, 9, 4, 6, 7};
int arrSize = sizeof(arr) / sizeof(arr[0]);
prevPermOpt1(arr, arrSize);
for (int i = 0; i < arrSize; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void PrevPermOpt1(int[] arr) {
int n = arr.Length;
for (int i = n - 2; i >= 0; --i) {
if (arr[i] > arr[i + 1]) {
for (int j = n - 1; j > i; --j) {
if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
(arr[i], arr[j]) = (arr[j], arr[i]);
return;
}
}
}
}
}
static void Main(string[] args) {
int[] arr = {1, 9, 4, 6, 7};
new Solution().PrevPermOpt1(arr);
Console.WriteLine(string.Join(" ", arr));
}
}The Python implementation involves iterating from the end, swapping elements, and breaking once the first valid pair is found, achieving the desired permutation.
Time Complexity: O(n), where n is the size of the array.
Space Complexity: O(1), as it operates in place without additional storage.
Approach 2: Optimal Swap Using Well-Placed Element
This alternative approach also involves iterating from the back of the given array. The goal is to identify two elements such that by swapping them, the resulting permutation is lexicographically smaller but largest among all possible permutations obtained by one swap.
The process involves identifying the position where the order breaks when the number prior is greater than any of the subsequent elements.
def prevPermOpt1(arr):
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 j > i and (arr[j] >= arr[i] or arr[j] == arr[j - 1]):
j -= 1
arr[i], arr[j] = arr[j], arr[i]
return arr
arr = [3, 2, 1]
print(prevPermOpt1(arr))import java.util.Arrays;
class Solution {
public void prevPermOpt1(int[] arr) {
int n = arr.length, i = n - 2;
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
if (i < 0) return;
int j = n - 1;
while (j > i && (arr[j] >= arr[i] || (j + 1 < n && arr[j] == arr[j + 1])))
j--;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {3, 2, 1};
sol.prevPermOpt1(arr);
System.out.println(Arrays.toString(arr));
}
}#include <vector>
#include <iostream>
class Solution {
public:
void prevPermOpt1(std::vector<int>& arr) {
int n = arr.size(), i = n - 2;
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
if (i < 0) return;
int j = n - 1;
while (j > i && (arr[j] >= arr[i] || arr[j] == arr[j - 1]))
j--;
std::swap(arr[i], arr[j]);
}
};
int main() {
std::vector<int> arr = {3, 2, 1};
Solution().prevPermOpt1(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}function prevPermOpt1(arr) {
let n = arr.length, i = n - 2;
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
if (i < 0) return arr;
let j = n - 1;
while (j > i && (arr[j] >= arr[i] || arr[j] === arr[j - 1]))
j--;
[arr[i], arr[j]] = [arr[j], arr[i]];
return arr;
}
console.log(prevPermOpt1([3, 2, 1]));#include <stdio.h>
void prevPermOpt1(int* arr, int arrSize){
int i = arrSize - 2;
while (i >= 0 && arr[i] <= arr[i + 1]) {
i--;
}
if (i < 0) return;
int j = arrSize - 1;
while (j > i && (arr[j] >= arr[i] || arr[j] == arr[j - 1])) {
j--;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int main() {
int arr[] = {3, 2, 1};
int arrSize = sizeof(arr) / sizeof(arr[0]);
prevPermOpt1(arr, arrSize);
for (int i = 0; i < arrSize; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void PrevPermOpt1(int[] arr) {
int n = arr.Length;
int i = n - 2;
while (i >= 0 && arr[i] <= arr[i + 1])
i--;
if (i < 0) return;
int j = n - 1;
while (j > i && (arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j - 1])))
j--;
(arr[i], arr[j]) = (arr[j], arr[i]);
}
static void Main(string[] args) {
int[] arr = {3, 2, 1};
new Solution().PrevPermOpt1(arr);
Console.WriteLine(string.Join(" ", arr));
}
}The Python approach is also focused on descending until a swap opportunity is evident and avoids leading to similar back outcomes.
Time Complexity: O(n), as two simple loops process the array quickly.
Space Complexity: O(1), using a direct swap in-memory without auxiliary data.
Approach 3: Greedy
First, we traverse the array from right to left, find the first index i that satisfies arr[i - 1] > arr[i], then arr[i - 1] is the number we need to swap. Next, we traverse the array from right to left again, find the first index j that satisfies arr[j] < arr[i - 1] and arr[j] neq arr[j - 1]. Now, we swap arr[i - 1] and arr[j] and return the array.
If we traverse the entire array and do not find an index i that meets the conditions, it means the array is already the smallest permutation, so we just return the original array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function prevPermOpt1(arr: number[]): number[] {
const n = arr.length;
for (let i = n - 1; i > 0; --i) {
if (arr[i - 1] > arr[i]) {
for (let j = n - 1; j > i - 1; --j) {
if (arr[j] < arr[i - 1] && arr[j] !== arr[j - 1]) {
const t = arr[i - 1];
arr[i - 1] = arr[j];
arr[j] = t;
return arr;
}
}
}
}
return arr;
}func prevPermOpt1(arr []int) []int {
n := len(arr)
for i := n - 1; i > 0; i-- {
if arr[i-1] > arr[i] {
for j := n - 1; j > i-1; j-- {
if arr[j] < arr[i-1] && arr[j] != arr[j-1] {
arr[i-1], arr[j] = arr[j], arr[i-1]
return arr
}
}
}
}
return arr
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Traversal for Optimal Swap | Time Complexity: O(n), where n is the size of the array. |
| Optimal Swap Using Well-Placed Element | Time Complexity: O(n), as two simple loops process the array quickly. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Swaps | O(n²) | O(1) | Useful for understanding permutation ordering or when constraints are very small |
| Reverse Traversal for Optimal Swap | O(n) | O(1) | General optimal solution expected in coding interviews |
| Optimal Swap Using Well-Placed Element | O(n) | O(1) | When you want a clearer greedy interpretation of selecting the best suffix candidate |
Frequently asked questions
Is Previous Permutation With One Swap easy or hard?
Previous Permutation With One Swap is typically rated Medium difficulty. The challenge lies in recognizing the permutation pattern and selecting the correct element to swap when duplicates exist in the suffix.
Previous Permutation With One Swap Python/Java solution
Python and Java implementations follow the same steps: identify the pivot index with reverse traversal, locate the best smaller element in the suffix, and swap them. Since the operation modifies the array directly, both implementations run in O(n) time with O(1) extra space.
How to solve Previous Permutation With One Swap in O(n)?
Traverse the array from the end to find the first index i where nums[i] > nums[i+1]. Then search the suffix for the largest element smaller than nums[i], taking care to handle duplicates correctly. Swap those two values and return the array. This greedy strategy ensures only one pass plus a small suffix scan, giving O(n) time.
What is the best approach for Previous Permutation With One Swap?
The best approach uses a greedy reverse traversal. Scan from right to left to find the first index where nums[i] > nums[i+1], then find the largest value smaller than nums[i] in the suffix and swap them. This produces the largest permutation smaller than the original in O(n) time and O(1) space.
Is Previous Permutation With One Swap asked at Google/Amazon/Meta?
Permutation and greedy array problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests understanding of lexicographic permutations, greedy selection, and efficient array traversal patterns.
What data structure is used in Previous Permutation With One Swap?
The problem primarily uses arrays with a greedy scanning technique. The algorithm relies on reverse traversal of the array and selecting the correct swap candidate from the suffix to maintain the largest possible smaller permutation.
What is the time complexity of Previous Permutation With One Swap?
The optimal solution runs in O(n) time because the array is scanned from right to left to find the pivot and then scanned again to find the best swap candidate. Space complexity is O(1) since the swap is performed in place without extra data structures.