Previous Permutation With One Swap - Solution & Explanation
Problem Statement
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.
The function prevPermOpt1 starts by iterating from the second last element to the first element to find a decreasing sequence. Once found, it searches from the end to find the largest element smaller than the found element to swap.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as it operates in-place.
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.
This C solution method identifies the decreasing point in the array from the end and searches for the best candidate to swap, ensuring not to swap with repeating identical elements.
Complexity
Time Complexity: O(n), due to the single pass traversal.
Space Complexity: O(1), as no extra space is needed.
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Reverse Traversal for Optimal Swap | Time Complexity: O(n), where n is the length of the array. |
| Optimal Swap Using Well-Placed Element | Time Complexity: O(n), due to the single pass traversal. |
| Greedy | — |
Detailed 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 |
Video Solution
Facebook Coding Interview Question | Leetcode 1053 | Previous Permutation With One Swap • WorkWithGoogler • 1,860 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Previous Permutation With One Swap easy or hard?
Previous Permutation With One Swap Python/Java solution
How to solve Previous Permutation With One Swap in O(n)?
What is the best approach for Previous Permutation With One Swap?
Is Previous Permutation With One Swap asked at Google/Amazon/Meta?
What data structure is used in Previous Permutation With One Swap?
What is the time complexity of Previous Permutation With One Swap?
Ready to solve this problem?
Practice Previous Permutation With One Swap with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor