Leetcode 1053: Previous Permutation With One Swap
Given an array of positive integers, return the lexicographically largest permutation that is smaller than the given array. This can be done by swapping exactly two elements. If no such swap is possible (i.e., the array is already the smallest permutation), return the same array.
Problem
Approach
Steps
Complexity
Input: You are given an array of integers arr where each element is a positive integer. You need to return the lexicographically largest permutation smaller than arr that can be made by swapping exactly two numbers in the array.
Example: Input: arr = [5, 3, 4, 2, 1]
Constraints:
• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^4
Output: The output should be the lexicographically largest permutation that is smaller than the given array, obtained by swapping exactly two elements. If no such swap exists, return the input array as is.
Example: Output: [5, 4, 3, 2, 1]
Constraints:
• The output is guaranteed to be a valid array of integers.
Goal: The goal is to find the lexicographically largest permutation smaller than the given array by swapping two elements.
Steps:
• 1. Find the first pair of adjacent elements where arr[i] > arr[i+1] (this is where the lexicographical order breaks).
• 2. Swap the first element arr[i] with the largest element in the suffix of the array that is smaller than arr[i].
• 3. If no such pair exists, return the array as is, because it is already the smallest permutation.
Goal: The array contains positive integers and its length is constrained as described below.
Steps:
• 1 <= arr.length <= 10^4
• 1 <= arr[i] <= 10^4
Assumptions:
• The array contains positive integers and the length of the array is between 1 and 10,000.
• Input: Input: arr = [5, 3, 4, 2, 1]
• Explanation: The largest permutation smaller than [5, 3, 4, 2, 1] is obtained by swapping 3 and 4, resulting in [5, 4, 3, 2, 1].
• Input: Input: arr = [1, 2, 3]
• Explanation: Since the array is already in ascending order, no swap can make a smaller permutation. Therefore, the output is the same as the input: [1, 2, 3].
Approach: The approach involves finding the first pair of adjacent elements where the order breaks and then swapping the first element with the largest element from the suffix of the array that is smaller than the first element. This ensures that the resulting permutation is the largest possible smaller permutation.
Observations:
• We need to identify the point where the permutation can be swapped to form a smaller arrangement.
• The array might already be in the smallest lexicographical order.
• The key is to find where the array stops being in descending order and use that information to swap the necessary elements.
Steps:
• 1. Start from the end of the array and look for the first element that is greater than the next one.
• 2. Once found, look for the largest element in the suffix that is smaller than the found element and swap them.
• 3. If no such pair exists, return the input array because it is already the smallest permutation.
Empty Inputs:
• There are no empty inputs because the array will always have at least one element.
Large Inputs:
• The algorithm needs to efficiently handle inputs up to 10,000 elements in length.
Special Values:
• If the array is already sorted in ascending order, no valid swap can be made.
Constraints:
• The array will always have positive integers.
vector<int> prevPermOpt1(vector<int>& arr) {
int idx = -1, n = arr.size();
for(int i = n - 1; i > 0; i--) {
// cout<< arr[i] << " " << arr[i - 1] << '\n';
if(arr[i] < arr[i - 1]) {
idx = i - 1;
break;
}
}
// cout << idx;
if(idx == -1) return arr;
for(int i = n - 1; i > idx; i--) {
if(arr[i] < arr[idx] && arr[i] != arr[i - 1]) {
swap(arr[i], arr[idx]);
break;
}
}
return arr;
}
1 : Function Definition
vector<int> prevPermOpt1(vector<int>& arr) {
This line defines the function `prevPermOpt1` which takes a reference to a vector of integers `arr` and returns a vector of integers. It aims to find the previous permutation of the array.
2 : Variable Initialization
int idx = -1, n = arr.size();
Here, `idx` is initialized to -1 to track the position where a decrease is found, and `n` stores the size of the array.
3 : Loop
for(int i = n - 1; i > 0; i--) {
This loop iterates through the array in reverse order, starting from the second last element and going towards the first.
4 : Condition
if(arr[i] < arr[i - 1]) {
This condition checks if the current element is smaller than the previous element. If true, it indicates a possible swap location.
5 : Update Index
idx = i - 1;
If a decrease is found, the index `idx` is set to `i - 1`, indicating the position where the swap needs to occur.
6 : Break Statement
break;
The loop breaks as soon as a decrease is found, as no further checking is needed.
7 : Edge Case Handling
if(idx == -1) return arr;
If no decrease is found (i.e., the array is sorted in ascending order), the function returns the original array, as no previous permutation exists.
8 : Second Loop
for(int i = n - 1; i > idx; i--) {
This second loop searches for the largest element smaller than `arr[idx]` to swap it with.
9 : Swap Condition
if(arr[i] < arr[idx] && arr[i] != arr[i - 1]) {
This condition ensures that the element to swap is smaller than `arr[idx]` and is not equal to the previous element, preventing unnecessary swaps.
10 : Swap Operation
swap(arr[i], arr[idx]);
The two elements at indices `i` and `idx` are swapped, creating the next smaller permutation.
11 : Break Statement
break;
The loop breaks once the swap is made, as only one swap is needed.
12 : Return Statement
return arr;
The function returns the modified array after the swap.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In all cases, we perform linear scans through the array, so the time complexity is O(n).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only need a constant amount of extra space, aside from the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus