Scale Engineer

Previous Permutation With One Swap

Med
#1005Time: 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: O(N), where N is the length of the array. This space is used to store copies of the array for permutations.
Patterns
Greedy
Data structures
Array

Prompt

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 <= 104
  • 1 <= arr[i] <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(N), where N is the length of the array. This space is used to store copies of the array for permutations.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem