Watch 10 video solutions for Previous Permutation With One Swap, a medium level problem involving Array, Greedy. This walkthrough by code_report has 6,396 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem 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 | 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 |