Previous Permutation With One Swap

Given an array of positive integers arr (not necessarily distinct), return the <span data-keyword="lexicographically-smaller-array">lexicographically</span>* 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]

For example:

1. arr = [3,2,1] should return [3,1,2] because swapping 2 and 1 makes a smaller array.
2. arr = [1,1,5] should return [1,1,5] because this is already the smallest permutation.
3. arr = [1,9,4,6,7] should return [1,7,4,6,9] because swapping 9 and 7 makes a smaller array.

## Problem Description

Given an array of positive integers `arr` (not necessarily distinct), the goal is to find the lexicographically largest permutation that is smaller than the input array `arr`, achievable with exactly one swap. If no such permutation exists, the function should return the original array.

## Brute Force Solution

A brute-force approach would involve generating all possible permutations of the array by swapping two elements at a time. Then, among all generated permutations, we find the largest one which is smaller than the original array.

```python
import itertools

def find_permutation_brute_force(arr):
    best_permutation = None
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            temp_arr = arr[:]
            temp_arr[i], temp_arr[j] = temp_arr[j], temp_arr[i]
            
            if temp_arr < arr and (best_permutation is None or temp_arr > best_permutation):
                best_permutation = temp_arr[:]
                
    return best_permutation if best_permutation else arr

# Example usage
arr = [1, 9, 4, 6, 7]
print(find_permutation_brute_force(arr)) # Output: [1, 7, 4, 6, 9]

Time Complexity: O(n^2) to iterate through all possible swaps and O(n) to copy the array for each swap, resulting in O(n^3). Additionally, comparison of arrays may take O(n). So, the overall complexity is approximately O(n^3).

Space Complexity: O(n) for storing the temporary array temp_arr and best_permutation.

This solution is inefficient and not optimal.

Optimal Solution

The optimal solution involves scanning the array from right to left and finding the first element that is greater than the element to its right. Let's call the index of this element 'i'. Then, scan the array from right to left again from index 'i + 1' to the end and find the largest element smaller than arr[i]. Swap these two elements.

def find_permutation(arr):
    n = len(arr)
    
    # Find the index i such that arr[i] > arr[i+1]
    i = n - 2
    while i >= 0 and arr[i] <= arr[i + 1]:
        i -= 1
    
    # If no such i exists, the array is non-increasing, return original array
    if i == -1:
        return arr
    
    # Find the index j of the largest element to the right of i that is smaller than arr[i]
    j = n - 1
    while j > i and arr[j] >= arr[i]:
        j -= 1
        
    # Swap arr[i] and arr[j]
    arr[i], arr[j] = arr[j], arr[i]
    
    return arr

# Example usage
arr = [1, 9, 4, 6, 7]
print(find_permutation(arr)) # Output: [1, 7, 4, 6, 9]

arr = [3, 2, 1]
print(find_permutation(arr)) # Output: [3, 1, 2]

arr = [1, 1, 5]
print(find_permutation(arr)) # Output: [1, 1, 5]

Big(O) Runtime Analysis

The algorithm iterates through the array at most twice. The first loop finds the index i, which takes O(n) time. The second loop finds the index j, which also takes O(n) time. The swap operation takes O(1) time. Therefore, the overall time complexity is O(n).

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space, regardless of the size of the input array. The space is used for variables such as i, j, and n. Therefore, the space complexity is O(1).

Edge Cases

1. Non-increasing array: If the input array is non-increasing (e.g., [5, 4, 3, 2, 1]), no swap will produce a lexicographically smaller permutation. The algorithm correctly identifies this case by checking if i is -1 after the first loop and returns the original array.
2. Array with duplicate elements: The algorithm correctly handles arrays with duplicate elements (e.g., [1, 2, 2, 3]). The second loop finds the rightmost largest element smaller than arr[i], ensuring the lexicographically largest permutation.
3. Array of length 1: If the array has only one element, no swap is possible, and the algorithm returns the original array because the first while loop will not be entered, i will remain -2, and i == -1 will become true.
4. Already smallest permutation: If the array represents the smallest possible permutation, no swap will create a smaller one. E.g. [1, 1, 5] remains [1, 1, 5].