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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Previous Permutation With One Swap

Number: 1139

Difficulty: Medium

Paid? No

Companies: Meta, Microsoft

Problem Description

Given an array of positive integers (which may contain duplicates), find the lexicographically largest permutation that is strictly smaller than the given array by performing exactly one swap between two elements. If no such swap exists – meaning the array is already the smallest possible permutation – then return the input array unchanged.

Key Insights

  • The goal is to make one swap that produces a permutation just smaller than the original, meaning the change must be minimal.
  • A greedy approach is useful: scan from right to left to locate the first pair where an element is greater than a following element.
  • Once the "pivot" element is identified, choose the best candidate from the right side – the largest number that is less than the pivot.
  • When duplicate values are present, ensure the swap uses the leftmost candidate among those equal to the chosen candidate to maximize the resulting permutation.

Space and Time Complexity

Time Complexity: O(n) – a single pass (or two passes) through the array is sufficient.
Space Complexity: O(1) – only a few extra variables are used.

Solution

The solution uses a greedy algorithm with the following steps:

  1. Traverse the array from right to left to find the first index (pivot) where arr[i-1] > arr[i]. This indicates an opportunity to make a swap that will lower the value slightly.
  2. From the subarray to the right of the pivot, identify the largest element that is less than arr[pivot] (i.e. arr[i-1]). If there are multiple occurrences of this candidate number, choose the leftmost occurrence to ensure the resulting permutation is as large as possible.
  3. Swap the pivot element with the chosen candidate and return the new array.
  4. If no pivot is found (i.e. the array is non-decreasing from left to right), then the array is already the smallest permutation; return it unchanged.

Data structures used are simple variables for indices and the input array itself. The approach is greedy and in-place, making it efficient for the problem constraints.

Code Solutions

# Python solution with detailed comments
class Solution:
    def prevPermOpt1(self, arr: List[int]) -> List[int]:
        n = len(arr)
        # Step 1: Find the pivot index where arr[index-1] > arr[index]
        pivot = -1
        for i in range(n - 1, 0, -1):
            if arr[i - 1] > arr[i]:
                pivot = i - 1
                break
        # If no pivot found, it is already the smallest permutation
        if pivot == -1:
            return arr
        
        # Step 2: Find the best candidate in arr[pivot+1:] which is the largest number less than arr[pivot]
        candidate_index = -1
        for j in range(n - 1, pivot, -1):
            # Check for candidate smaller than arr[pivot]
            if arr[j] < arr[pivot]:
                # Ensure we choose the leftmost occurrence if duplicates exist
                if candidate_index == -1 or arr[j] > arr[candidate_index]:
                    candidate_index = j
        
        # Step 3: Swap the pivot element with the candidate element
        arr[pivot], arr[candidate_index] = arr[candidate_index], arr[pivot]
        return arr
← Back to All Questions