BinarySearch 0709 Next Smaller Permutation

Problem statement

https://binarysearch.com/problems/Next-Smaller-Permutation/

Solution

Equal to Leetcode 1053. Previous Permutation With One Swap, but here we need a bit more efficient algorithm, because values can be any, not digits.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        i = len(A) - 2
        while i >= 0 and A[i] <= A[i+1]: i -= 1

        if i >= 0:
            idx = i + 1
            for j in range(idx, len(A)):
                if A[idx] < A[j] < A[i]: idx = j
            A[idx], A[i] = A[i], A[idx]
        return A