#1053

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Previous Permutation With One Swap

Find the lexicographically largest permutation smaller than the given array using exactly one swap, leveraging a greedy approach.

array greedy

Problem Statement

Given an array of positive integers arr (not necessarily distinct), determine the lexicographically largest permutation smaller than arr achievable with exactly one swap of two elements. If no such permutation exists, return the original array. A swap exchanges the values at positions arr[i] and arr[j].

For example, given arr = [3,2,1], swapping 2 and 1 produces [3,1,2], the largest permutation smaller than the original. Similarly, arr = [1,1,5] cannot be improved, and arr = [1,9,4,6,7] swaps 9 and 7 to yield [1,7,4,6,9]. Constraints: 1 <= arr.length <= 10^4 and 1 <= arr[i] <= 10^4.

Examples

Example 1

Input: arr = [3,2,1]

Output: [3,1,2]

Swapping 2 and 1.

Example 2

Input: arr = [1,1,5]

Output: [1,1,5]

This is already the smallest permutation.

Example 3

Input: arr = [1,9,4,6,7]

Output: [1,7,4,6,9]

Swapping 9 and 7.

Constraints

1 <= arr.length <= 104
1 <= arr[i] <= 104

Solution Approach

Identify Decreasing Point

Traverse the array from right to left to find the first index i where arr[i] > arr[i+1]. This is the pivot for a swap because only positions after i can produce a smaller permutation.

Select Largest Smaller Candidate

Scan right of index i to find the largest number smaller than arr[i], ensuring the swap yields the lexicographically largest previous permutation. Pick the rightmost such number to maintain maximality.

Perform Swap and Validate

Swap arr[i] with the selected candidate and return the new array. If no valid swap exists, return the original array. This respects the greedy invariant and guarantees correctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since we scan the array twice: once to find the pivot and once to select the swap candidate. Space complexity is O(1) as we perform swaps in-place without extra structures.

What Interviewers Usually Probe

Can you find a single swap that reduces the permutation while keeping it maximal?
How do you efficiently locate the candidate for swapping to preserve lexicographic order?
What invariant ensures that your swap choice produces the largest smaller permutation?

Common Pitfalls or Variants

Common pitfalls

Swapping with the first smaller element instead of the largest smaller one can produce a suboptimal result.
Not scanning from right to left may miss the pivot producing the largest decrease.
Failing to handle duplicate numbers correctly can lead to incorrect swaps.

Follow-up variants

Previous permutation allowing multiple swaps instead of exactly one.
Next permutation with one swap using a similar greedy selection but reversed criteria.
Finding the k-th previous permutation under a single-swap constraint.

FAQ

What is the main pattern to recognize in Previous Permutation With One Swap?

Identify a rightmost decrease where a single swap can produce a smaller permutation, following a greedy choice to select the largest smaller candidate.

How do duplicates affect swapping decisions?

You must select the rightmost largest smaller duplicate to ensure maximal lexicographic order; swapping with an earlier duplicate may yield a suboptimal result.

Can this algorithm handle arrays of length 10^4 efficiently?

Yes, the method scans the array twice linearly, achieving O(n) time and O(1) space, suitable for large arrays.

What if the array is already the smallest permutation?

No valid swap exists; the algorithm correctly returns the original array unchanged.

Why is a greedy choice plus invariant validation crucial here?

It ensures the selected swap produces the largest possible previous permutation without violating the single-swap requirement.

terminal

Solution

Solution 1: Greedy

First, we traverse the array from right to left, find the first index $i$ that satisfies $arr[i - 1] > arr[i]$, then $arr[i - 1]$ is the number we need to swap. Next, we traverse the array from right to left again, find the first index $j$ that satisfies $arr[j] < arr[i - 1]$ and $arr[j] \neq arr[j - 1]$. Now, we swap $arr[i - 1]$ and $arr[j]$ and return the array.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1054 distant barcodes #1029 two city scheduling #1024 video stitching