PROBLEM LINK:
Author: shakil ahmed
DIFFICULTY:
SUMPLE-EASY
PREREQUISITES:
Greedy
PROBLEM:
Given an array and an integer K. In array consecutive pairs of elements can be swapped. Need to find the lexicographical minimal array after at most K-swaps.
EXPLANATION:
We can use a greedy algorithm to solve this problem.
For N elements let us assume array consist of { a1 , a2 , …, an }.
If we can replace any value ai with a1 that will give a lexicographically smaller array compared to original one. For any element ai to replace with a1 we need i - 1 swaps since we can only swap adjacent elements. But the maximum swap we can do is K so all we need to do is to choose the minimum element in the sub-array {a1, a2, …, ak+1}. If ai is the minimum element, we move it to the position of a1 and shift the rest elements by one. The number of swaps taken will be i - 1. Assuming K > i - 1, we can repeat the same process for a2 as long as we completely exhaust K. This does not guarantees us the lexicographically minimum array, but it does guarantee the minimum possible array with at most K swaps. The notable point is some times you don’t really need to use all the swaps.For example, in an array {1, 2, 3, 5, 4} and K = 5 we can achieve lexicographically minimum array {1, 2, 3, 4, 5} in only one swap. The time complexity using this greedy approach is O (N^2) which is good enough for N <= 1000.
Example,
For the given sample testcase N = 5, K = 3 and array being {8, 9, 11, 2, 1}. We start from a1 i.e. 8 and do a linear scan for all elements uptil K i.e. until a4. The minimum ai is a4 , so the new array is {2, 8, 9, 11, 1} and K is updated to K - i - 1 i.e. 0. Since we exhausted K, {2, 8, 9, 11, 1} is the final array we should return.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.