Previous Permutation With One Swap: Greedy Array Strategy

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, return the same array.

This is LeetCode 1053: Previous Permutation With One Swap, and it tests whether you understand greedy reasoning over permutations. The problem is the mirror image of Next Permutation, and the approach follows a similar pattern of scanning from the right to find the right position to modify.

Why this problem matters

Permutation problems appear constantly in interviews. Next Permutation (LeetCode 31) asks you to find the next larger permutation. This problem asks for the previous smaller one. Understanding both directions shows a deep grasp of lexicographic ordering and greedy decision-making. The same scanning patterns show up in problems involving sorted suffixes, prefix optimization, and greedy swaps.

The key insight

To make the array lexicographically smaller with one swap, you need to place a smaller value at some position and push the larger value to the right. But you want the result to be as large as possible (the largest permutation that is still smaller). That means:

1. You should modify a position as far right as possible. Changing an earlier position causes a bigger drop.
2. At that position, you should swap with the largest available value that is still strictly smaller. A bigger replacement keeps the result closer to the original.
3. If there are duplicate candidates with the same value, pick the leftmost one. Putting the larger displaced element further to the right keeps the permutation larger.

These three greedy choices pin down a unique answer.

The solution

def prevPermOpt1(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 arr[j - 1] == arr[j]:
        j -= 1

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

The first while loop scans from right to left looking for the descent: the rightmost index i where arr[i] is strictly greater than arr[i + 1]. Everything to the right of i is non-decreasing, meaning that portion is already at its minimum permutation. You cannot make the array smaller by swapping within that region alone.

If no descent exists (i drops below 0), the array is non-decreasing and already the smallest permutation. Return it as-is.

When a descent exists, the second while loop finds the rightmost element that is strictly less than arr[i]. Because the suffix from i+1 onward is non-decreasing, scanning from the right and stopping at the first value less than arr[i] gives us the largest such value.

The third while loop handles duplicates. If there are multiple elements with the same value as arr[j], we move j left to the first occurrence. Swapping with the leftmost duplicate ensures the displaced larger element ends up as far to the right as possible, maximizing the resulting permutation.

Finally, we swap arr[i] and arr[j] and return.

Visual walkthrough

Let's trace through arr = [3, 2, 4, 3, 1] step by step.

After the swap, the array becomes [3, 2, 3, 4, 1]. That is the lexicographically largest permutation that is still smaller than the original, achievable with a single swap.

Complexity

Time is O(n). Finding the descent scans at most n elements. Finding the swap candidate scans at most n elements. The duplicate skip is bounded by the same scan. Total work is at most 3n comparisons and one swap.

Space is O(1). The swap is done in-place. Only a few index variables are used.

The building blocks

This problem is built from two reusable patterns that appear across many greedy and array problems.

Rightmost descent detection

Scanning from right to left to find the first place where the array "drops" is the same brick used in Next Permutation. There, you look for an ascending pair. Here, you look for a descending pair. The logic is identical: walk backward until you find the boundary between the "already optimized" suffix and the position you can improve. This pattern appears in problems about monotonic sequences, next greater elements, and any problem that asks you to find the rightmost position where a change is beneficial.

Greedy swap selection

Once you know where to make the swap, choosing what to swap in is a classic greedy choice. You want the largest value that is still strictly smaller than the current one. This "largest but smaller" pattern appears in problems like finding floor values in sorted arrays, successor/predecessor queries in BSTs, and interval scheduling.

Edge cases

• Already the smallest permutation. When the array is non-decreasing like [1, 2, 3], no descent exists and you return the array unchanged.
• Two elements. For [2, 1], the descent is at index 0. The swap candidate is index 1. Swap to get [1, 2]. For [1, 2], no descent exists. Return [1, 2].
• Duplicates at the swap position. For [1, 9, 4, 4, 2], the descent is at index 1 (arr[1]=9 is greater than arr[2]=4). The largest value less than 9 is 4, which appears at indices 2 and 3. Pick the leftmost (index 2) to get [1, 4, 9, 4, 2].
• All elements the same. An array like [5, 5, 5] has no descent (no index where arr[i] is strictly greater than arr[i+1]). Return the array unchanged.
• Descent at the very beginning. For [3, 1], the descent is at index 0. The only candidate is index 1. Swap to get [1, 3].

From understanding to recall

You understand the algorithm. You can trace through examples. But will you remember the details under interview pressure?

The tricky parts are small: using strict greater-than when finding the descent, scanning from the right for the swap candidate, and handling the leftmost-duplicate edge case. These are not conceptual gaps. They are recall gaps. And recall gaps close with repetition.

This algorithm is composed of two building blocks: rightmost descent detection and greedy swap selection. Each piece is small enough to drill on its own. When both are automatic, the full solution writes itself.

Related posts

• Next Permutation - The mirror problem. Find the next larger permutation using the same suffix analysis pattern, but in the opposite direction.
• Sort Colors - Another in-place array problem that uses careful index management and greedy partitioning.
• Wiggle Sort II - Greedy placement decisions in an array where relative ordering matters.

CodeBricks breaks Previous Permutation With One Swap into its rightmost descent detection and greedy swap selection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until it is automatic. When the problem shows up in your interview, you do not think about it. You just write it.