We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Previous Permutation With One Swap

Difficulty: Medium

Problem Description

Given an array of positive integers arr (not necessarily distinct), return the lexicographically largest permutation that is smaller than arr, that can be made with exactly one swap. If it cannot be done, then return the same array.

Key Insights

  • The goal is to find a permutation that is smaller than the current one through a single swap.
  • The largest permutation smaller than a given one can typically be found by identifying the rightmost pair of elements where the left element is greater than the right element.
  • To maximize the result after the swap, the larger element should be swapped with the largest possible element on its right that is smaller than it.
  • If no such pair exists, the input array is the smallest permutation and should be returned as is.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To find the previous permutation with one swap:

  1. Traverse the array from the end to find the first pair (arr[i], arr[i+1]) where arr[i] > arr[i+1]. This identifies the point where the order can be altered to create a smaller permutation.
  2. If no such pair is found, return the original array as it is already the smallest permutation.
  3. If a pair is found, find the largest element to the right of arr[i] that is smaller than arr[i].
  4. Swap these two elements.
  5. Return the modified array.

The algorithm primarily utilizes a single pass to identify the swap positions and another pass to find the correct swap candidate, resulting in an overall linear complexity.

Code Solutions

def previousPermutation(arr):
    n = len(arr)
    
    # Step 1: Find the first decreasing element from the right
    i = n - 2
    while i >= 0 and arr[i] <= arr[i + 1]:
        i -= 1
    
    # If no such element is found, return the original array
    if i == -1:
        return arr
    
    # Step 2: Find the largest element to the right of arr[i] that is smaller than arr[i]
    j = n - 1
    while arr[j] >= arr[i]:
        j -= 1
    
    # Step 3: Swap arr[i] and arr[j]
    arr[i], arr[j] = arr[j], arr[i]
    
    return arr
← Back to All Questions