Find the Largest lexicographic array with at most K consecutive swaps
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
Reading time: 30 minutes
For a given array, find the largest lexicographic array which can be obtained from it after performing K consecutive swaps. Given two arrays A1 and A2, A1 is defined to be lexicographically larger than A2 if for the first i (from 0 to length of smaller array), element at index i is greater than element at index i of A2.
Note you can do less than K swaps as forcing K swaps may reduce the largeness of the result array.
We will solve this using:
- a naive approach O(N!) time
- Greedy approach O(N^2) time
Example to understand the problem
Consider the following array:
A1 = [1, 33, 44, 11, 2, 5]
A2 = [1, 39, 20, 1, 0, 4]
A2 is lexicographically larger than A1 as for index 1, 39 > 33.
A3 = [2, 99, 100]
A3 is lexicographically smaller than A1 and A2 as length of A3 is smaller than length of A1 and A2.
For the problem, consider this example:
A1 = [3, 5, 1, 4]
The lexicographically largest array is:
[5, 4, 3, 1]
With 1 consecutive swap, the largest lexicographically largest array is:
[5, 3, 1, 4]
With 2 consecutive swaps, the largest lexicographically largest array is:
[5, 3, 4, 1]
The lexicographically largest array for the input array is:
And, the lexicographically largest array after 1 consecutive swap is:
Naive Approach O(N!)
A naive approach would be to generate all permutations of the array and selecting the one which satisfies the condition of K consequtive swaps.
Generation of all permutations takes n! time.
The steps involved are:
- Generate all permutations of the array.
- Count the number of swaps.
- If number of swaps is less than or equal to K, update lexicographically largest array.
Pseudocode:
Input: array[]
1. Generate all perumations of the array using some function(like next permutation)
2 Count the number of swaps:
(a)Loop through the length of the array and compare with original array.
3. If the current array is lexicographically larger than the array:
(i)Update the array lexicograph_max[]
Algorithm O(N^2)
We implement a greedy approach which runs as long as the value of the counter variable for swaps is less than K and the array is not lexicographically largest.
The algorithm goes as follows:
- Loop from the 0-th index of the array to the last index of the array as long as K is non-zero.
- For each element, find the largest element in the array which is greater than the current element and can be swapped with the current element in at most K swaps.
- Swap the found element with the current element and update the value of K.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
//Obtaining length of array and number of allowed swaps
int n, k;
cin >> n >> k;
int a[n];
//Taking input of array elements
for(int i=0; i<n; i++){
cin >> a[i];
}
//Swapping elements while k is non-zero
for(int i=0; i<n-1 && k>0; i++){
//Initializing temporary index to current index
int in = i;
for(int j=i+1; j<n; j++){
//Break if max swaps are exceeded
if(k<j-i) break;
//Update maximum element index
if(a[j]>a[in]){
in = j;
}
}
//Swap the elements from in to the i-th index
for(int j=in;j>i;j--){
swap(a[j], a[j-1]);
}
//Update k after swapping in-i elements
k -= in-i;
}
//Printing lexicographically largest array
for(int i=0;i<n;i++) cout << a[i] << " ";
return 0;
}
Examples
//Console input
5 3
3 5 4 1 2
//Console output
5 4 3 2 1
Here is the state of the array for all iterations:
- In the first iteration, the first and second elements are swapped.
- In the second iteration, the second and third elements are swapped.
- In the third iteration, the fourth and fifth elements are swapped.
Complexity
The time complexity of this algorithm is O(N^2)
.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.