Formatted question description: https://leetcode.ca/all/1053.html

1053. Previous Permutation With One Swap (Medium)

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 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

 

Note:

  1. 1 <= A.length <= 10000
  2. 1 <= A[i] <= 10000

Related Topics:
Array, Greedy

Solution 1.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int first = -1, second;
        for (int i = A.size() - 1; i > first; --i) {
            while (i - 1 > first && A[i - 1] == A[i]) --i;
            int j = i - 1;
            while (j > first && A[j] <= A[i]) --j;
            if (j > first) {
                first = j;
                second = i;
            }
        }
        if (first > -1) swap(A[first], A[second]);
        return A;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        stack<pair<int, int>> s;
        int first = -1, second = -1;
        for (int i = 0; i < A.size(); ++i) {
            while (s.size() && A[i] >= s.top().second) s.pop();
            if (s.size() && (s.top().first >= second || (s.top().first == first && A[i] != A[second]))) {
                first = s.top().first;
                second = i;
            }
            s.emplace(i, A[i]);
        }
        if (first > -1) swap(A[first], A[second]);
        return A;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int i = A.size() - 2;
        while (i >= 0 && A[i] <= A[i + 1]) --i;
        if (i < 0) return A;
        int j = i + 1;
        for (int k = i + 2; k < A.size() && A[k] < A[i]; ++k) {
            if (A[k] > A[j]) j = k;
        }
        swap(A[i], A[j]);
        return A;
    }
};

Solution 4.

// OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int i = A.size() - 2;
        while (i >= 0 && A[i] <= A[i + 1]) --i;
        if (i < 0) return A;
        auto j = lower_bound(A.begin() + i + 1, A.end(), A[i]) - 1;
        auto k = lower_bound(A.begin() + i + 1, j, *j);
        swap(A[i], *k);
        return A;
    }
};

Java

  • class Solution {
        public int[] prevPermOpt1(int[] A) {
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>((a, b) -> (a[0] - b[0]));
            int swapIndex = -1;
            int swapNum = 0;
            int length = A.length;
            for (int i = length - 1; i > 0; i--) {
                int num = A[i];
                priorityQueue.offer(new int[]{num, i});
                if (num < A[i - 1]) {
                    swapIndex = i - 1;
                    swapNum = A[i - 1];
                    break;
                }
            }
            if (swapIndex < 0)
                return A;
            int nextSwapNum = 0, nextSwapIndex = -1;
            while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] < swapNum) {
                int[] numIndex = priorityQueue.poll();
                nextSwapNum = numIndex[0];
                nextSwapIndex = numIndex[1];
            }
            A[swapIndex] = nextSwapNum;
            A[nextSwapIndex] = swapNum;
            return A;
        }
    }
    
  • // OJ: https://leetcode.com/problems/previous-permutation-with-one-swap/
    // Time: O(N^2)
    // Space: O(1)
    class Solution {
    public:
        vector<int> prevPermOpt1(vector<int>& A) {
            int first = -1, second;
            for (int i = A.size() - 1; i > first; --i) {
                while (i - 1 > first && A[i - 1] == A[i]) --i;
                int j = i - 1;
                while (j > first && A[j] <= A[i]) --j;
                if (j > first) {
                    first = j;
                    second = i;
                }
            }
            if (first > -1) swap(A[first], A[second]);
            return A;
        }
    };
    
  • # 1053. Previous Permutation With One Swap
    # https://leetcode.com/problems/previous-permutation-with-one-swap/
    
    class Solution:
        def prevPermOpt1(self, arr: List[int]) -> List[int]:
            n = len(arr)
            if n <= 1: return arr
            
            index = -1
            for i in range(n - 1, 0, -1):
                if arr[i] < arr[i - 1]:
                    index = i - 1
                    break
                    
            if index == -1: return arr
            for i in range(n - 1, index - 1, -1):
                if arr[i] < arr[index] and arr[i] != arr[i - 1]:
                    arr[i], arr[index] = arr[index], arr[i]
                    break
            
            return arr
            
    
    

All Problems

All Solutions