Skip to content

1053. Previous Permutation With One Swap 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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