# Previous Permutation With One Swap
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/previous-permutation-with-one-swap)
Canonical: https://scaleengineer.com/dsa/problems/previous-permutation-with-one-swap
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## 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 <= 104`
* `1 <= arr[i] <= 104`

# Approaches
## Brute Force by Trying All Swaps
This approach exhaustively tries every possible single swap. For each swap, it checks if the resulting permutation is smaller than the original. Among all such valid smaller permutations, it keeps track of the lexicographically largest one.
**Time:** O(N^3). There are O(N^2) pairs to swap. For each swap, copying the array and comparing it takes O(N) time. · **Space:** O(N), where N is the length of the array. This space is used to store copies of the array for permutations.
**Pros:** Simple to conceptualize and implement.; Guaranteed to find the correct answer by checking all possibilities.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method systematically explores all potential solutions. We can iterate through every possible pair of distinct indices `(i, j)` in the array. For each pair, we perform a swap. This creates a new permutation. We then check if this new permutation is lexicographically smaller than the original array. If it is, we compare it against the best result we've found so far. The 'best' result is the smaller permutation that is lexicographically the largest. We continue this process for all pairs, ensuring we find the optimal one. If no swap results in a smaller permutation, it means the array is already the smallest possible, and we return it unchanged.

```java
class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int[] bestPermutation = arr;
        boolean found = false;

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int[] currentPermutation = arr.clone();
                swap(currentPermutation, i, j);

                if (isSmaller(currentPermutation, arr)) {
                    if (!found || isSmaller(bestPermutation, currentPermutation)) {
                        bestPermutation = currentPermutation;
                        found = true;
                    }
                }
            }
        }
        return bestPermutation;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private boolean isSmaller(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] < b[i]) return true;
            if (a[i] > b[i]) return false;
        }
        return false; // they are equal
    }
}
```
### Algorithm
- Initialize a variable `bestPermutation` to hold the result. Initially, it can be a copy of the original array or a null value.
- Generate every possible pair of indices `(i, j)` where `i < j`.
- For each pair, create a new array `currentPermutation` by swapping `arr[i]` and `arr[j]`.
- Check if `currentPermutation` is lexicographically smaller than the original `arr`.
- If it is smaller, compare it with `bestPermutation`. If `currentPermutation` is lexicographically larger than `bestPermutation`, update `bestPermutation` to `currentPermutation`.
- After checking all pairs, if a smaller permutation was found, `bestPermutation` will hold the largest one. Otherwise, it will still be the original array.

## Single Pass Greedy Approach
A much more efficient approach uses a greedy, single-pass strategy. To get the largest permutation that is smaller than the input, we want to make a change as far to the right as possible. This minimizes the impact on the more significant (left-side) digits. This involves finding a 'pivot' element that can be swapped with a smaller element to its right to create a smaller permutation, while carefully choosing the swap element to ensure the result is as large as possible.
**Time:** O(N), where N is the length of the array. We perform at most two linear scans of the array. · **Space:** O(1), as the swap is performed in-place and only a few variables are used for indices.
**Pros:** Highly efficient with linear time complexity.; Uses constant extra space.; Optimal solution for the given constraints.
**Cons:** The logic can be tricky to derive, especially handling duplicate values correctly.
### Explanation
This optimized approach avoids brute force by making intelligent choices based on the properties of lexicographical order. 

First, we find the rightmost element `arr[i]` that is larger than its right neighbor `arr[i+1]`. This index `i` is our pivot. Making a swap at this position, while keeping the prefix `arr[0...i-1]` unchanged, ensures we find a permutation that is just slightly smaller than the original, and it will be larger than any permutation created by a swap at an index less than `i`. If no such `i` exists, the array is sorted non-decreasingly (e.g., `[1,1,5]`), and no smaller permutation is possible.

Second, after finding the pivot `i`, we must choose an element `arr[j]` from the suffix `arr[i+1...n-1]` to swap with `arr[i]`. To maximize the new permutation, the new `arr[i]` should be as large as possible, which means we must find the largest value in the suffix that is still smaller than the original `arr[i]`. We search for this value and its index `j`.

Finally, we swap `arr[i]` and `arr[j]` to get the final result.

```java
class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return arr;
        }

        // Step 1: Find the largest index i such that arr[i] > arr[i+1]
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) {
            i--;
        }

        // If no such index exists, the array is already the smallest permutation
        if (i < 0) {
            return arr;
        }

        // Step 2: Find the index j of the largest element to the right of i that is smaller than arr[i]
        // We want the leftmost occurrence of that value to maximize the permutation.
        int j = i + 1;
        for (int k = i + 2; k < n; k++) {
            if (arr[k] < arr[i] && arr[k] > arr[j]) {
                j = k;
            }
        }

        // Step 3: Swap the elements at i and j
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        return arr;
    }
}
```
### Algorithm
- **Step 1: Find Pivot `i`**: Scan the array from right to left, starting from the second-to-last element. Find the first index `i` such that `arr[i] > arr[i+1]`. This is our 'pivot'. If no such index is found, the array is already the smallest permutation, so return it.
- **Step 2: Find Swap Element `j`**: Scan the array from right of the pivot `i` to the end. We need to find an element `arr[j]` to swap with `arr[i]`. To make the resulting permutation as large as possible, `arr[j]` must be the largest value in the suffix `arr[i+1...n-1]` that is strictly smaller than `arr[i]`. To handle duplicates correctly (which would result in an even larger permutation), we must pick the leftmost occurrence of this value.
- **Step 3: Swap**: Swap the elements at index `i` and the found index `j`.
- **Step 4: Return**: The modified array is the desired result.

# Solutions
### Java

```java
class Solution {
public
  int[] prevPermOpt1(int[] arr) {
    int n = arr.length;
    for (int i = n - 1; i > 0; --i) {
      if (arr[i - 1] > arr[i]) {
        for (int j = n - 1; j > i - 1; --j) {
          if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
            int t = arr[i - 1];
            arr[i - 1] = arr[j];
            arr[j] = t;
            return arr;
          }
        }
      }
    }
    return arr;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> prevPermOpt1(vector<int> &arr) {
    int n = arr.size();
    for (int i = n - 1; i > 0; --i) {
      if (arr[i - 1] > arr[i]) {
        for (int j = n - 1; j > i - 1; --j) {
          if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
            swap(arr[i - 1], arr[j]);
            return arr;
          }
        }
      }
    }
    return arr;
  }
};

```

### Python

```python
class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]: n = len(arr) for i in range(n - 1, 0, - 1): if arr[i - 1] > arr[i]: for j in range(n - 1, i - 1, - 1): if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]: arr[i - 1], arr[j] = arr[j], arr[i - 1] return arr return arr

```