Jobs

Interviews

Discussions

Previous Permutation With One Swap

Medium

Asked by:

78 views

Topics:

ArraysGreedy Algorithms

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.

Note that a swap exchanges the positions of two numbers arr[i] and arr[j]

Example 1:

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Constraints:

1 <= arr.length <= 10⁴
1 <= arr[i] <= 10⁴

Try coding it in LeetCode

Previous Permutation With One Swap

Medium

Asked by:

78 views

Topics:

ArraysGreedy Algorithms

Note that a swap exchanges the positions of two numbers arr[i] and arr[j]

Example 1:

Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:

Input: arr = [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:

Input: arr = [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Constraints:

1 <= arr.length <= 10⁴
1 <= arr[i] <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input array is already the smallest possible permutation?
Can the input array contain duplicate numbers?
Is the input array guaranteed to have at least two elements?
Are the numbers in the array integers?
What range of values can the integers in the input array have?

Brute Force Solution

Approach

The brute force approach to finding the previous permutation involves checking every possible swap. We try swapping every pair of numbers and see if the resulting permutation is both smaller than the original and also the closest to the original.

Here's how the algorithm would work step-by-step:

Go through every possible pair of numbers in the list.
For each pair, imagine swapping them.
Check if the result of this swap is smaller than the original list.
If it's not smaller, then that swap is no good, so move to the next pair.
If it is smaller, compare it to the best (closest to original) smaller list we've found so far.
If this newly swapped list is better (closer to the original) than the best one we've found, replace the best one with this new one.
After checking all the possible swaps, use the best one we found. If no swap made it smaller, there's no answer, return original list.

Code Implementation

def previous_permutation_with_one_swap_brute_force(numbers):
    best_permutation = list(numbers)
    found_smaller = False

    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            
            #Create a copy to simulate the swap
            temp_numbers = list(numbers)
            temp_numbers[first_index], temp_numbers[second_index] = temp_numbers[second_index], temp_numbers[first_index]

            # Check if the swapped permutation is smaller
            if temp_numbers < numbers:
                
                # If no smaller permutation has been found yet, or the current one is larger than the previous best
                if not found_smaller or temp_numbers > best_permutation:
                    best_permutation = temp_numbers
                    found_smaller = True

    # If a smaller permutation was found, return it, otherwise return the original list
    if found_smaller:
        return best_permutation
    else:
        return numbers

Big(O) Analysis

Time Complexity

O(n²) – The described solution iterates through every possible pair of numbers in the input list of size n. Finding all pairs requires a nested loop structure: the outer loop iterates through the list, and the inner loop checks the remaining elements to form a pair. Therefore, for each of the n elements, the algorithm potentially compares it with the other (n-1) elements. This results in approximately n * (n-1) / 2 comparisons, which simplifies to O(n²).

Space Complexity

O(N) – The described brute force approach implicitly creates a copy of the input list during each potential swap to compare against the original and the best swap so far. In the worst-case scenario, a temporary list of size N (where N is the length of the input list) will be created for each possible swap to hold the result of the swap operation. Although many of these copies might be overwritten the space is at least temporarily utilized. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To find the previous permutation with a single swap, we look for the rightmost place where the sequence decreases. Then, we find the largest element to the right of that place that is smaller than the element at that place and swap them.

Here's how the algorithm would work step-by-step:

Start from the end of the list and move backwards.
Find the first number that is smaller than the number right next to it.
If you reach the beginning of the list without finding such a number, then the list is already in ascending order, and no previous permutation exists, so you can't do anything.
Now, look at the part of the list to the right of the number you found.
Find the largest number in that right part that is still smaller than the number you found earlier.
Swap these two numbers.
You now have the previous permutation with one swap.

Code Implementation

def previous_permutation(numbers):
    list_length = len(numbers)
    
    for i in range(list_length - 2, -1, -1):
        # Find the first element smaller than its next.
        if numbers[i] > numbers[i + 1]:
            
            right_part_index = i + 1
            largest_smaller_index = i + 1
            
            # Find largest in right part but smaller than numbers[i].
            while right_part_index < list_length:
                if numbers[right_part_index] < numbers[i]:
                    largest_smaller_index = right_part_index
                else:
                    break
                right_part_index += 1

            # Swap the two numbers to get previous permutation.
            numbers[i], numbers[largest_smaller_index] = numbers[largest_smaller_index], numbers[i]
            return numbers

    # No such previous permutation exists.
    return numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates backward through the array of size n to find the first decreasing element. In the worst case, this takes O(n) time. After finding the decreasing element, it iterates through a portion of the array to the right to find the largest element smaller than the decreasing element. This second iteration is also bounded by O(n). Since the operations are sequential, we add the runtimes, resulting in O(n) + O(n) = O(n).

Space Complexity

O(1) – The algorithm operates in-place, modifying the input list directly. It only requires a few constant extra variables to keep track of indices during the search and swap operations. These variables, such as indices for identifying the decreasing point and the element to swap, take up a fixed amount of space irrespective of the input list's size, N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return the input array immediately as no swap is possible.
Array with only one element	Return the input array as no swap is possible with only one element.
Array already in strictly descending order	Return the input array as no swap can result in a lexicographically smaller permutation.
Array with all identical elements	Return the input array as no swap will change the permutation.
Array with two elements in ascending order	Swap the two elements to create the previous permutation.
Large array with numbers near integer limits	Ensure no integer overflow occurs during comparison, which the provided problem does not contain so should be ignored.
Array contains duplicate elements preventing a larger swap	Iterate from right to left, selecting the rightmost swap that gives the largest lexicographical order, handling duplicates by prioritizing the rightmost smaller element for the swap.
Input array is very large, close to the maximum allowed size	The solution should have O(n) time complexity, so processing large arrays should not cause excessive delays.

Null or empty input array

How to Handle:

Return the input array immediately as no swap is possible.

Array with only one element

How to Handle:

Return the input array as no swap is possible with only one element.

Array already in strictly descending order

How to Handle:

Return the input array as no swap can result in a lexicographically smaller permutation.

Array with all identical elements

How to Handle:

Return the input array as no swap will change the permutation.

Array with two elements in ascending order

How to Handle:

Swap the two elements to create the previous permutation.

Large array with numbers near integer limits

How to Handle:

Ensure no integer overflow occurs during comparison, which the provided problem does not contain so should be ignored.

Array contains duplicate elements preventing a larger swap

How to Handle:

Iterate from right to left, selecting the rightmost swap that gives the largest lexicographical order, handling duplicates by prioritizing the rightmost smaller element for the swap.

Input array is very large, close to the maximum allowed size

How to Handle:

The solution should have O(n) time complexity, so processing large arrays should not cause excessive delays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input array is already the smallest possible permutation?
Can the input array contain duplicate numbers?
Is the input array guaranteed to have at least two elements?
Are the numbers in the array integers?
What range of values can the integers in the input array have?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through every possible pair of numbers in the list.
For each pair, imagine swapping them.
Check if the result of this swap is smaller than the original list.
If it's not smaller, then that swap is no good, so move to the next pair.
If it is smaller, compare it to the best (closest to original) smaller list we've found so far.
If this newly swapped list is better (closer to the original) than the best one we've found, replace the best one with this new one.
After checking all the possible swaps, use the best one we found. If no swap made it smaller, there's no answer, return original list.

Code Implementation

def previous_permutation_with_one_swap_brute_force(numbers):
    best_permutation = list(numbers)
    found_smaller = False

    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            
            #Create a copy to simulate the swap
            temp_numbers = list(numbers)
            temp_numbers[first_index], temp_numbers[second_index] = temp_numbers[second_index], temp_numbers[first_index]

            # Check if the swapped permutation is smaller
            if temp_numbers < numbers:
                
                # If no smaller permutation has been found yet, or the current one is larger than the previous best
                if not found_smaller or temp_numbers > best_permutation:
                    best_permutation = temp_numbers
                    found_smaller = True

    # If a smaller permutation was found, return it, otherwise return the original list
    if found_smaller:
        return best_permutation
    else:
        return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start from the end of the list and move backwards.
Find the first number that is smaller than the number right next to it.
If you reach the beginning of the list without finding such a number, then the list is already in ascending order, and no previous permutation exists, so you can't do anything.
Now, look at the part of the list to the right of the number you found.
Find the largest number in that right part that is still smaller than the number you found earlier.
Swap these two numbers.
You now have the previous permutation with one swap.

Code Implementation

def previous_permutation(numbers):
    list_length = len(numbers)
    
    for i in range(list_length - 2, -1, -1):
        # Find the first element smaller than its next.
        if numbers[i] > numbers[i + 1]:
            
            right_part_index = i + 1
            largest_smaller_index = i + 1
            
            # Find largest in right part but smaller than numbers[i].
            while right_part_index < list_length:
                if numbers[right_part_index] < numbers[i]:
                    largest_smaller_index = right_part_index
                else:
                    break
                right_part_index += 1

            # Swap the two numbers to get previous permutation.
            numbers[i], numbers[largest_smaller_index] = numbers[largest_smaller_index], numbers[i]
            return numbers

    # No such previous permutation exists.
    return numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return the input array immediately as no swap is possible.
Array with only one element	Return the input array as no swap is possible with only one element.
Array already in strictly descending order	Return the input array as no swap can result in a lexicographically smaller permutation.
Array with all identical elements	Return the input array as no swap will change the permutation.
Array with two elements in ascending order	Swap the two elements to create the previous permutation.
Large array with numbers near integer limits	Ensure no integer overflow occurs during comparison, which the provided problem does not contain so should be ignored.
Array contains duplicate elements preventing a larger swap	Iterate from right to left, selecting the rightmost swap that gives the largest lexicographical order, handling duplicates by prioritizing the rightmost smaller element for the swap.
Input array is very large, close to the maximum allowed size	The solution should have O(n) time complexity, so processing large arrays should not cause excessive delays.

Null or empty input array

How to Handle:

Return the input array immediately as no swap is possible.

Array with only one element

How to Handle:

Return the input array as no swap is possible with only one element.

Array already in strictly descending order

How to Handle:

Return the input array as no swap can result in a lexicographically smaller permutation.

Array with all identical elements

How to Handle:

Return the input array as no swap will change the permutation.

Array with two elements in ascending order

How to Handle:

Swap the two elements to create the previous permutation.

Large array with numbers near integer limits

How to Handle:

Ensure no integer overflow occurs during comparison, which the provided problem does not contain so should be ignored.

Array contains duplicate elements preventing a larger swap

How to Handle:

Iterate from right to left, selecting the rightmost swap that gives the largest lexicographical order, handling duplicates by prioritizing the rightmost smaller element for the swap.

Input array is very large, close to the maximum allowed size

How to Handle:

The solution should have O(n) time complexity, so processing large arrays should not cause excessive delays.