1053. Previous Permutation With One Swap LeetCode Solution

In this guide, you will get 1053. Previous Permutation With One Swap LeetCode Solution with the best time and space complexity. The solution to Previous Permutation With One Swap problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Previous Permutation With One Swap solution in C++
Previous Permutation With One Swap solution in Java
Previous Permutation With One Swap solution in Python
Additional Resources

1053. Previous Permutation With One Swap LeetCode Solution image

Problem Statement of Previous Permutation With One Swap

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

Complexity Analysis

Time Complexity:
Space Complexity:

1053. Previous Permutation With One Swap LeetCode Solution in C++

class Solution {
 public:
  vector<int> prevPermOpt1(vector<int>& arr) {
    const int n = arr.size();
    int l = n - 2;
    int r = n - 1;

    while (l >= 0 && arr[l] <= arr[l + 1])
      l--;
    if (l < 0)
      return arr;
    while (arr[r] >= arr[l] || arr[r] == arr[r - 1])
      r--;
    swap(arr[l], arr[r]);

    return arr;
  }
};
/* code provided by PROGIEZ */

1053. Previous Permutation With One Swap LeetCode Solution in Java

class Solution {
  public int[] prevPermOpt1(int[] arr) {
    final int n = arr.length;
    int l = n - 2;
    int r = n - 1;

    while (l >= 0 && arr[l] <= arr[l + 1])
      l--;
    if (l < 0)
      return arr;
    while (arr[r] >= arr[l] || arr[r] == arr[r - 1])
      r--;
    swap(arr, l, r);

    return arr;
  }

  private void swap(int[] arr, int l, int r) {
    int temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;
  }
}
// code provided by PROGIEZ

1053. Previous Permutation With One Swap LeetCode Solution in Python

class Solution:
  def prevPermOpt1(self, arr: list[int]) -> list[int]:
    n = len(arr)
    l = n - 2
    r = n - 1

    while l >= 0 and arr[l] <= arr[l + 1]:
      l -= 1
    if l < 0:
      return arr
    while arr[r] >= arr[l] or arr[r] == arr[r - 1]:
      r -= 1
    arr[l], arr[r] = arr[r], arr[l]

    return arr
 # code by PROGIEZ