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.
Which type of traversal does breadth first search do?
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
arrand store it in variablen. - Start iterating over the array backwards using a
forloop, checking each adjacent pair(arr[i - 1], arr[i])to find the first instance wherearr[i - 1]is greater thanarr[i]. This means thatarr[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 toi - 1. - Inside this nested loop, we look for an element
arr[j]that is smaller thanarr[i - 1]but also is not equal toarr[j - 1](to handle duplicates). We are trying to find the highest valued element smaller thanarr[i - 1]to make the simplest swap. - Once the correct element to swap with is found (
arr[j]), we swaparr[i - 1]witharr[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.
What's the relationship between a tree and a graph?
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
arrwhich is5in 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 find3is greater than2, which means we have our pivot element3at index0. - Now, we need to find the best candidate to swap with
3to get the lexicographically next smaller permutation. So, we start another loop from the end to the index just right of our pivot (index1). - As we iterate, we look for an element smaller than our pivot
3, so we consider5, but it's not smaller. We move to4and1. We find1fulfills our condition, being smaller than3and also not repeated. It is the largest number smaller than3to the right of the pivot. - We swap the pivot
3with the number1, 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
231class 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}
291class 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};
301function 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}
30How many ways can you arrange the three letters A, B and C?
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.
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.