Previous Permutation With One Swap - Leetcode Solution

Problem Statement:

Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]). If it cannot be done, then return the same array.

Example:

Input: [3,2,1] Output: [3,1,2] Explanation: Swap 2 and 1.

Input: [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation.

Input: [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swap 9 and 7.

Solution:

To solve the problem, we first need to check if there is a number x which is greater than the number after it, i.e A[i] > A[i+1]. If there is no such number, it means the given array A is already the lexicographically smallest permutation and we return the same. If there is such a number, then we need to find the largest number y < A[i] to swap with A[i]. Once we find y, we swap A[i] and A[j] and return the array.

To find the number y, we start from the end of the array and search for the first number which is smaller than A[i]. This can be done by keeping track of the maximum number seen so far and finding the first number which is smaller than the maximum. Once we find the number y, we swap A[i] and A[j] and return the array.

Code:

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size();
        int i = n-2;
        while (i>=0 && A[i] <= A[i+1])
            i--;
        if (i == -1)
            return A;
        int j = n-1;
        while (j > i && A[j] >= A[i])
            j--;
        while (j > i+1 && A[j-1] == A[j])
            j--;
        swap(A[i], A[j]);
        return A;
    }
};

1