Lexicographically smallest array after consecutive swaps

December 30, 2021

Lexicographically smallest array after consecutive swaps

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

Lexicographically smallest 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 smallest 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 smallest arrangement of the array we will fix a position ‘i’ of the 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 smallest(int arr[], int n, int k)
{
    for (int i = 0; i<n – 1 & k> 0; i++)
    {
        int cur = i;
        //Find Smallest 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];

    smallest(arr, n, k);

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

Output