Previous Permutation With One Swap

MEDIUM

Description

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 <= 10⁴
1 <= arr[i] <= 10⁴

Approaches

Checkout 2 different approaches to solve Previous Permutation With One Swap. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(N), where N is the length of the array. This space is used to store copies of the array for permutations.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Previous Permutation With One Swap. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Previous Permutation With One Swap

Patterns:

Greedy

Data Structures:

Array