1053. Previous Permutation With One Swap

Problem Description

Given an array of positive integers arr, the objective is to find the lexicographically largest permutation that is smaller than arr, with the condition that only one swap of two elements is allowed. If no such permutation exists (meaning arr is the smallest possible permutation), then the function should return the array as it is.

A permutation is considered lexicographically smaller if at the first position where the two permutations differ, the number in the smaller permutation is smaller than in the larger one. In simpler terms, it's similar to the alphabetical order, but with numbers.

The problem includes a swap operation, which involves exchanging the positions of two numbers in the array: arr[i] and arr[j].

Intuition

To solve this problem, we need to think in reverse order, starting from the last element towards the first element of the array. Our goal is to find the first pair where the left element is greater than the right element (arr[i - 1] > arr[i]). This specific pair gives us the point beyond which all elements are in non-increasing order.

Once we have that pivot, we need to find the largest possible number to the right of it that is still smaller than the pivot number itself, because we want the largest permutation smaller than the current array. We must also take care of duplicates because swapping with a duplicate won't change the permutation.

We iterate from the end of the array until we find an element that satisfies these conditions. We swap these two elements (the pivot and the chosen element to its right) and return the modified array. If the loop finishes without finding such an element, no swap can satisfy the condition, and the input array is returned unchanged as it's already the smallest permutation.

Learn more about Greedy patterns.

Solution Approach

To implement the solution, we use a simple approach to iterate through the array without any complicated data structures or patterns. Here's a step-by-step breakdown of what the given Python function does:

Determine the length of the given arr and store it in variable n.
Start iterating over the array backwards using a for loop, checking each adjacent pair (arr[i - 1], arr[i]) to find the first instance where arr[i - 1] is greater than arr[i]. This means that arr[i - 1] is our potential element to be swapped as we aim to make the largest number smaller.
When we find such an element at arr[i - 1], we need to find the best candidate to swap it with to get the lexicographically next smaller permutation. To do this, another loop iterates over the array from the end to i - 1.
Inside this nested loop, we look for an element arr[j] that is smaller than arr[i - 1] but also is not equal to arr[j - 1] (to handle duplicates). We are trying to find the highest valued element smaller than arr[i - 1] to make the simplest swap.
Once the correct element to swap with is found (arr[j]), we swap arr[i - 1] with arr[j] and return the array immediately.
If no such element is found while iterating, it means the array is already the smallest permutation possible with the given digits, so we return the original array without any modifications.

The solution's time complexity is O(n^2) in the worst case, where n is the size of the array. This occurs when we need to perform a nested loop iteration for every element in the array. However, on average, the time complexity could be better if the swap is found early.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an example array arr = [3, 2, 1, 4, 5] and illustrate the solution approach to find the lexicographically largest permutation that is smaller than arr using only one swap.

Determine the length of arr which is 5 in this case.
Start iterating from the end to find the first adjacent pair where the left number is greater than the right number. We compare the pairs (5, 4), (4, 1), (1, 2), and finally (2, 3). Upon comparing (2, 3), we find 3 is greater than 2, which means we have our pivot element 3 at index 0.
Now, we need to find the best candidate to swap with 3 to get the lexicographically next smaller permutation. So, we start another loop from the end to the index just right of our pivot (index 1).
As we iterate, we look for an element smaller than our pivot 3, so we consider 5, but it's not smaller. We move to 4 and 1. We find 1 fulfills our condition, being smaller than 3 and also not repeated. It is the largest number smaller than 3 to the right of the pivot.
We swap the pivot 3 with the number 1, resulting in the array [1, 2, 3, 4, 5].
Return the modified array, which is now [1, 2, 3, 4, 5]. This is the lexicographically largest permutation smaller than the original array which could be achieved through a single swap.

Summarizing the steps with the chosen array:

Identify pivot (3) which is greater than its right neighbor (2).
Find the best swap candidate (1) which is smaller than the pivot but still the largest on the right.
Swap pivot with the candidate and return the result.

In this example, the iterations and swap were straightforward and led us to the lexicographically largest permutation smaller than the original array by just moving the pivot 3 to the position of 1. The original array is left in an increasing order, as expected after the swap.

Solution Implementation

1class Solution:
2    def prevPermOpt1(self, arr):
3        # Length of the array
4        length = len(arr)
5
6        # Loop backwards through the array starting from the second last element
7        for i in range(length - 1, 0, -1):
8            # Check if the current element is greater than its following element
9            # meaning a smaller permutation is possible
10            if arr[i - 1] > arr[i]:
11                # Find the element to swap with, which is the rightmost element 
12                # that is smaller than arr[i - 1] and not a duplicate of its previous element
13                for j in range(length - 1, i - 1, -1):
14                    # Swap the elements arr[i - 1] and arr[j] only if arr[j] is
15                    # smaller than arr[i - 1] and different from arr[j - 1]
16                    if arr[j] < arr[i - 1] and arr[j] != arr[j - 1]:
17                        arr[i - 1], arr[j] = arr[j], arr[i - 1]  # Perform the swap
18                        return arr  # Return the updated array
19
20        # If no permutation could be performed that makes the original array smaller,
21        # then return the original array itself
22        return arr
23

1class Solution {
2    public int[] prevPermOpt1(int[] arr) {
3        // Get the length of the array.
4        int arrayLength = arr.length;
5      
6        // Start from the end of the array and look for the first pair where
7        // the previous element is greater than the current element.
8        for (int i = arrayLength - 1; i > 0; --i) {
9            if (arr[i - 1] > arr[i]) {
10                // We found a pair, now start from the end of the array again
11                // and look for an element that is smaller than the element at
12                // index i - 1 but not the same as its previous element (to avoid duplicates).
13                for (int j = arrayLength - 1; j > i - 1; --j) {
14                    if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
15                        // Swap the elements at i - 1 and j.
16                        int temp = arr[i - 1];
17                        arr[i - 1] = arr[j];
18                        arr[j] = temp;
19                        // Return the modified array.
20                        return arr;
21                    }
22                }
23            }
24        }
25        // If no swap was done, return the original array.
26        return arr;
27    }
28}
29

1class Solution {
2public:
3    vector<int> prevPermOpt1(vector<int>& arr) {
4        int length = arr.size();
5        // Start from the end of the array and move backwards.
6        for (int i = length - 1; i > 0; --i) {
7            // If the current element is less than its previous one,
8            // a swap is possible to get the previous permutation.
9            if (arr[i - 1] > arr[i]) {
10                // Look for the largest element which is smaller than arr[i - 1]
11                // starting from the end of the array.
12                for (int j = length - 1; j > i - 1; --j) {
13                    // Ensure that we get the largest element which is not equal to
14                    // its previous element to handle duplicates.
15                    // This ensures the previous permutation is the largest one that is smaller than the current.
16                    if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
17                        // Swap the found element with arr[i - 1] to get the correct previous permutation.
18                        swap(arr[i - 1], arr[j]);
19                        // Return the modified array as the result, no further action needed.
20                        return arr;
21                    }
22                }
23            }
24        }
25        // If no previous permutation is possible (array is sorted in increasing order),
26        // return the unchanged array.
27        return arr;
28    }
29};
30

1function prevPermOpt1(arr: number[]): number[] {
2    // Calculate the length of the array just once to improve performance
3    const length = arr.length;
4  
5    // Start looking for the element to swap from the end of the array
6    for (let i = length - 1; i > 0; --i) {
7        // Check if the current element is less than its previous element, indicating a swap is possible
8        if (arr[i - 1] > arr[i]) {
9          
10            // Iterate over the array from the end to the current element
11            for (let j = length - 1; j > i - 1; --j) {
12                // Find the rightmost element that is smaller than the element at i - 1 and not a duplicate
13                if (arr[j] < arr[i - 1] && arr[j] !== arr[j - 1]) {
14                  
15                    // Perform the swap by exchanging values of arr[i - 1] and arr[j]
16                    let temp = arr[i - 1];
17                    arr[i - 1] = arr[j];
18                    arr[j] = temp;
19                  
20                    // Return the modified array as no further swaps are needed
21                    return arr;
22                }
23            }
24        }
25    }
26  
27    // If no suitable previous permutation is found, return the original array
28    return arr;
29}
30

Time and Space Complexity

The time complexity of the provided code is O(n^2) in the worst case. This complexity arises from the fact that we have a nested loop where the outer loop runs backwards through the list arr starting from the second last element to the first, and the inner loop also runs backwards, starting from the last element until it finds an element less than arr[i - 1]. The worst-case scenario occurs when we have to iterate over the entire array for the inner loop for each element in the outer loop.

The space complexity of the code is O(1) as we are only using a constant amount of extra space. The swapping of elements is done in-place and does not require any additional data structures that are dependent on the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: