Problem statement

https://leetcode.com/problems/previous-permutation-with-one-swap/

Solution

We need to find two places i and j, such that:

  1. arr[i] > arr[j]
  2. i is as right as possible.
  3. We look for the biggest digit smaller than arr[i] to the right of i.
  4. For fixed digit we want to have the rightest place.

So we traverse from the end, for each digit keeping the leftest index so far. For each place i we look for digit smaller than arr[i] and we start from biggest digits first.

Complexity

It is O(n * 10) for time and O(n) for space.

Code

class Solution:
    def prevPermOpt1(self, arr):
        n = len(arr)
        d = {}
        for i in range(n - 1, -1, -1):
            d[arr[i]] = i
            for dig in range(arr[i] - 1, -1, -1):
                if dig in d:
                    arr[i], arr[d[dig]] = arr[d[dig]], arr[i]
                    return arr
                
        return arr