Code Implementation

class Solution:
    def prevPermOpt1(self, arr):
        n = len(arr)
        # Step 1: Find the first index from the right where arr[i] > arr[i+1]
        i = n - 2
        while i >= 0 and arr[i] <= arr[i+1]:
            i -= 1
        if i < 0:
            return arr
        # Step 2: Find the largest index j > i such that arr[j] < arr[i]
        j = n - 1
        while arr[j] >= arr[i] or (j > 0 and arr[j] == arr[j-1]):
            j -= 1
        # Step 3: Swap arr[i] and arr[j]
        arr[i], arr[j] = arr[j], arr[i]
        return arr
      

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = arr.size();
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;
        int j = n - 1;
        while (arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j - 1])) j--;
        swap(arr[i], arr[j]);
        return arr;
    }
};
      

class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        int i = n - 2;
        while (i >= 0 && arr[i] <= arr[i + 1]) i--;
        if (i < 0) return arr;
        int j = n - 1;
        while (arr[j] >= arr[i] || (j > 0 && arr[j] == arr[j - 1])) j--;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }
}
      

var prevPermOpt1 = function(arr) {
    let n = arr.length;
    let i = n - 2;
    while (i >= 0 && arr[i] <= arr[i + 1]) i--;
    if (i < 0) return arr;
    let j = n - 1;
    while (arr[j] >= arr[i] || (j > 0 && arr[j] === arr[j - 1])) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];
    return arr;
};
      

Problem Description

You are given an array arr of positive integers representing a permutation of numbers. Your task is to return the lexicographically largest permutation that is smaller than the current array, using exactly one swap (or no swap if not possible). In other words, you can swap at most one pair of elements to produce the previous permutation in lexicographical order. If no such permutation exists (i.e., the array is already the smallest), return the array as is.

• Only one swap is allowed, and the result must be the largest possible permutation that is still smaller than the original.
• If there are duplicate elements, you must not swap to a permutation with the same elements as before (i.e., do not swap equal elements if it would not change the array).
• Input: arr (list of integers)
• Output: Modified arr (list of integers)

Thought Process

First, let's think about what it means to find the "previous permutation" with one swap. If we try every possible pair of indices and swap them, then check which result is the largest but still less than the original, that would work but be very inefficient.

Instead, let's look for a pattern. In the "Next Permutation" problem, we look for the first decrease from the right. Here, we want the previous permutation, so we look for the first increase from the right — that is, the first place where arr[i] > arr[i+1]. This is the point where a swap can make the array smaller.

Once we've found this index, we want to swap it with the largest possible element to its right that is still less than arr[i] (to make the result as large as possible, but still smaller). If there are duplicates, we take the leftmost such element (to avoid swapping equal elements).

This thought process shifts us from brute-force (try all swaps) to a targeted, linear-time approach.

Solution Approach

• Step 1: Find the Pivot Point.
  • Scan the array from right to left and find the first index i where arr[i] > arr[i+1].
  • This is the point where the array can be made smaller by swapping.
  • If no such index exists, the array is already the smallest permutation.
• Step 2: Find the Swap Candidate.
  • From the end of the array, look for the largest index j such that arr[j] < arr[i].
  • If there are multiple candidates with the same value, pick the leftmost one (to avoid swapping equal elements and producing the same array).
• Step 3: Swap and Return.
  • Swap arr[i] and arr[j].
  • Return the modified array.

This approach works in a single pass from right to left and ensures we only make one swap to get the desired result.

Example Walkthrough

Let's walk through an example with arr = [3, 2, 1]:

1. Start from the right. Compare 2 and 1: 2 > 1. So, i = 1 is our pivot.
2. Now, scan from the end to find the largest j such that arr[j] < arr[i] (i.e., arr[j] < 2).
   • arr[2] = 1 < 2, so j = 2.
3. Swap arr[1] and arr[2] to get [3, 1, 2].
4. The result [3, 1, 2] is the largest permutation smaller than [3, 2, 1] with one swap.

If the array was already sorted in increasing order (e.g., [1, 2, 3]), no such i exists, so we return the original array.

Time and Space Complexity

• Brute-force Approach:
  • Try every possible swap: O(n²) time, as there are O(n²) pairs.
  • Space: O(1) extra (in-place), but inefficient due to time.
• Optimized Approach (as above):
  • Time: O(n), since we scan from right to left at most twice.
  • Space: O(1), as we swap in-place without extra data structures.

The optimized approach is much faster and suitable for large arrays.

Summary

The key insight is to find the first place from the right where the permutation can be made smaller, and then swap it with the largest possible smaller value to its right. This ensures the result is the largest permutation less than the original, using only one swap. The elegant, linear-time solution leverages properties of permutations and lexicographical order, making the algorithm both efficient and easy to implement.