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] <= 104To solve #1053 Previous Permutation With One Swap, the goal is to create the largest permutation that is smaller than the current array using exactly one swap. This can be approached using a greedy observation about how permutations decrease.
Start scanning the array from right to left to find the first index where the order breaks the non‑decreasing pattern (i.e., a position where arr[i] > arr[i+1]). This index represents the first place where reducing the value can produce a smaller permutation.
Next, search to the right of this index to find the largest value smaller than arr[i]. When duplicates exist, careful selection is required so that the swap produces the closest smaller permutation rather than a much smaller one.
Finally, perform a single swap between these two elements. Because the scan is linear and only a constant amount of extra memory is required, the algorithm is efficient and suitable for interview settings.
Time Complexity: O(n) Space Complexity: O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy scan with one swap | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You need to swap two values, one larger than the other. Where is the larger one located?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of permutation and greedy swap problems are common in technical interviews. Companies often test understanding of permutation logic, greedy decisions, and careful handling of duplicates.
No special data structure is required. The problem can be solved using simple array traversal and index tracking, making it efficient with constant extra space.
The optimal approach uses a greedy scan from right to left. First find the first index where the array decreases, then swap it with the largest smaller element on its right. This ensures the result is the closest smaller permutation possible with one swap.
Scanning from the right helps identify the first position where the permutation can be decreased while keeping the result as large as possible. This ensures the resulting array is the immediate previous permutation rather than a much smaller one.