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 variablen
. - Start iterating over the array backwards using a
for
loop, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 is5
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 find3
is greater than2
, which means we have our pivot element3
at index0
. - 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 (index1
). - As we iterate, we look for an element smaller than our pivot
3
, so we consider5
, but it's not smaller. We move to4
and1
. We find1
fulfills our condition, being smaller than3
and also not repeated. It is the largest number smaller than3
to the right of the pivot. - We swap the pivot
3
with 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
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.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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