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>& A) {
    const int n = A.size();
    int l = n - 2;
    int r = n - 1;

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

    return A;
  }
};
 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[] A) {
    final int n = A.length;
    int l = n - 2;
    int r = n - 1;

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

    return A;
  }

  private void swap(int[] A, int l, int r) {
    int temp = A[l];
    A[l] = A[r];
    A[r] = temp;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def prevPermOpt1(self, A: List[int]) -> List[int]:
    n = len(A)
    l = n - 2
    r = n - 1

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

    return A