Lexicographically Largest array after consecutive swaps

December 30, 2021

Lexicographically Largest array after consecutive swaps

In the Lexicographically Largest array after consecutive swaps problem, we have to find the largest array possible obtained after swapping array elements. The problem can be optimally solved using a greedy technique. In this article, we will provide a C++ solution with an explanation.

Lexicographically Largest array after consecutive swaps

Lexicographically Largest array after consecutive swaps Problem Description

Given an array of n integers and an integer k. You can swap any two consecutive elements of the array. The operation can be performed at most k times. Output the lexicographically largest array possible.

Input

  • First Line contains two integers n & k – the size of array & the number of swaps.
  • Next Line contains n integers – the elements of the array.

Output

  • Single line output containing n integers.

Solution

To find the lexicographically largest arrangement of the array we will fix a position ‘i’ of array and try to find the best smallest position ‘j’ such that j > i & arr[j] > arr[i].

After finding appropriate j , we just have to elements from i to j-1, one position right and move element at j to i.

Time Complexity – O(n*k)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
void largest(int arr[], int n, int k)
{
    for (int i = 0; i<n – 1 & k> 0; i++)
    {
        int cur = i;
        //Find Largest after position i
        for (int j = i + 1; j < n; j++)
        {
            if (j – i > k)
                break;
            if (arr[j] > arr[cur])
                cur = j;
        }
        for (int j = cur; j > i; j–)
        {
            swap(arr[j], arr[j – 1]);
        }
        k -= (cur – i);
    }
}
int main()
{
    int n, k;
    cin >> n >> k;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    largest(arr, n, k);

    for (int i = 0; i < n; i++)
        cout << arr[i] << ” “;
    cout << endl;
    return 0;
}

Output

5 2
1 2 3 4 5
3 1 2 4 5