# LeetCode 1053: Previous Permutation With One Swap

## Problem Restatement

We are given an array of positive integers `arr`.

We need to return the lexicographically largest permutation smaller than `arr` that can be obtained with at most one swap.

If not possible, return `arr`.

The official constraints state that `1 <= arr.length <= 10^4` and `1 <= arr[i] <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr` |
| Output | Previous permutation with at most one swap |

Function shape:

```python
def prevPermOpt1(arr: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
arr = [3, 2, 1]
```

Previous: `[3, 1, 2]`. One swap of index 1 and 2.

Answer:

```python
[3, 1, 2]
```

Example 2:

```python
arr = [1, 1, 5]
```

For `arr = [1, 1, 5]`, the array is already in nondecreasing order. No single swap can produce a lexicographically smaller permutation, so we return the array unchanged.

Answer for `[1, 1, 5]`:

```python
[1, 1, 5]
```

## Key Insight

To get the previous permutation with one swap:
1. Find the rightmost position `i` where `arr[i] > arr[i+1]` (a descent). If none, already the smallest.
2. Find the largest `arr[j]` to the right of `i` that is less than `arr[i]`. Among equal values, pick the leftmost (to avoid duplicate swaps).
3. Swap `arr[i]` with `arr[j]`.

## Correctness

We want the largest permutation smaller than `arr`. The rightmost descent is the best place to make a swap (affects only the suffix). Swapping with the largest value smaller than `arr[i]` to its right gives the lexicographically largest decrease.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear scans |
| Space | `O(1)` | In-place |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def prevPermOpt1(self, arr: list[int]) -> list[int]:
        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 arr[j] >= arr[i]:
            j -= 1

        while j > 0 and arr[j] == arr[j - 1]:
            j -= 1

        arr[i], arr[j] = arr[j], arr[i]
        return arr
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.prevPermOpt1([3,2,1]) == [3,1,2]
    assert s.prevPermOpt1([1,1,5]) == [1,1,5]
    assert s.prevPermOpt1([1,9,4,6,7]) == [1,7,4,6,9]
    assert s.prevPermOpt1([3,1,1,3]) == [1,3,1,3]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `[3,2,1]` | `[3,1,2]` | Swap last two |
| `[1,1,5]` | `[1,1,5]` | Already minimum |
| `[1,9,4,6,7]` | `[1,7,4,6,9]` | Swap 9 with 7 |
| `[3,1,1,3]` | `[1,3,1,3]` | Rightmost descent found |