Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1139. Previous Permutation With One Swap

My accepted Python solution to LeetCode problem 1139, Previous Permutation With One Swap, running in 0ms.

  • Difficulty: Medium
  • Python
  • Runtime 0ms
  • Memory 18.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 0ms, memory 18.2MB, accepted 2026-01-02.

python
class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        # Find the first index from right where arr[i] > arr[i+1]
        i = n - 2
        while i >= 0 and arr[i] <= arr[i + 1]:
            i -= 1
        
        if i < 0:
            return arr
        
        # Find the largest element smaller than arr[i] in arr[i+1:]
        # If there are duplicates, pick the leftmost one
        j = i + 1
        best_j = j
        best_val = arr[j]
        for k in range(i + 1, n):
            if arr[k] < arr[i] and arr[k] > best_val:
                best_val = arr[k]
                best_j = k
            elif arr[k] == best_val:
                # Keep the leftmost one (don't update best_j)
                pass
        
        # Swap
        arr[i], arr[best_j] = arr[best_j], arr[i]
        return arr

Source