Get this book -> Problems on Array: For Interviews and Competitive Programming

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)`

.