Lexicographically Smallest Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
OlaNosh technologiesNokia

Problem statement

You have been given an array/list ARR consisting of ‘N’ integers. You are also given a positive integer ‘K’.

Your task is to find the lexicographically smallest ARR that can be obtained by swapping at most K consecutive elements.

An array/list P is lexicographically smaller than its permutation Q if and only if, for the earliest index at which P and Q differ, P's element at that index is smaller than Q's element at that index. Example, P = [1, 12, 4, 7, 8] is lexicographically smaller than Q = [1, 12, 8, 4, 7].

For example, if ARR = [70, 60, 90, 21, 11] and K = 3, then-

Swap 1: We swap adjacent elements 90 and 21. So, ARR after one swap is [70, 60, 21, 90, 11].
Swap 2: We swap adjacent elements 60 and 21. So, ARR after one swap is [70, 21, 60, 90, 11].
Swap 3: We swap adjacent elements 70 and 21. So, ARR after one swap is [21, 70, 60, 90, 11].
The lexicographically smallest ARR after K = 3 swaps is [21, 70, 60, 90, 11].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘K’ representing the size of the array/list and the given integer, respectively.

The second line of each test case contains ‘N’ single space-separated integers representing the array elements.
Output Format : 
For each test case, print the lexicographically smallest array/list obtained after at most K swaps.

Note :

You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 5000
1 <= K <= 10^9 
0 <= ARR[i] <= 10^5

 Where 'ARR[i]' denotes the ith elements of the given array/list.

Time Limit: 1sec
Sample Input 1 :
2
4 2
3 5 1 4
5 5
1 3 5 7 9
Sample Output 1 :
1 3 5 4
1 3 5 7 9

Sample Output 1 Explanation:

Test Case 1:
Given ARR = [3, 5, 1, 4] and K = 2.
Swap 1: We swap consecutive elements 1 and 5. So, ARR after one swap is [3, 1, 5, 4].
Swap 2: We swap consecutive elements 1 and 3. So, ARR after one swap is [1, 3, 5, 4].
The lexicographically smallest ARR after K = 2 swaps is [1, 3, 5, 4].

Test Case 2:
The given ARR is already sorted in ascending order, which is the lexicographically smallest arrangement possible.
Sample Input 2 :
1
5 1
39 28 20 17 16
Sample Output 2 :
28 39 20 17 16
Hint

Think of finding a minimum element at distance ‘K’ and bringing it to the desired position.

Approaches (1)
Greedy Approach

Looking at the problem, we observe that-

  • The lexicographically smallest ARR is obtained if the smallest element is present at the beginning i.e ARR[0], followed by the next smallest at index 1 (ARR[1]) and so on.
  • The number of swaps to move an element from index ‘i’ to index ‘j’ (where i > j) is i - j as we can swap only neighbouring elements.
  • The maximum swaps allowed are ‘K’.

 

Keeping the above points in mind -

  1. We traverse ARR from beginning to end till K is greater than 0.
    1. We find the index of the smallest element (say ‘minIndex’) at distance ‘K’ from ARR[i + 1].
    2. We then swap all consecutive elements from minIndex to i.
    3. We update the number of swaps left (K) to K - (minIndex - I).
  2. Finally, we return the updated ARR as our answer.
Time Complexity

O(N^2), where N is the number of elements in the given array/list.

 

Finding the smallest element from ‘i+1’ to ‘N’ and then bringing it to position ‘i’ by swapping consecutive elements takes O(N) time. In the worst case (ARR sorted in descending order), when K is greater than or equal to N*(N-1)/2, the outer loop will run O(N) times. Thus, the overall time complexity is O(N^2).

Space Complexity

O(1), constant space is used.

Code Solution
(100% EXP penalty)
Lexicographically Smallest Array
Full screen
Console