Lexicographically Smallest Array Problem Statement
You are given an array ARR
of 'N' integers and a positive integer 'K'.
Your task is to determine the lexicographically smallest array that can be obtained by performing at most 'K' swaps of consecutive elements.
Example:
Input:
ARR = [70, 60, 90, 21, 11], K = 3
Output:
[21, 70, 60, 90, 11]
Explanation:
You perform following swaps to achieve this:
- Swap 1: Swap 90 and 21 to get [70, 60, 21, 90, 11].
- Swap 2: Swap 60 and 21 to get [70, 21, 60, 90, 11].
- Swap 3: Swap 70 and 21 to get [21, 70, 60, 90, 11].
The resultant array is the lexicographically smallest one after at most 3 swaps.
Input:
The first line of input contains an integer 'T' representing the number of test cases. For each test case:
- The first line contains two integers 'N' and 'K'.
- The second line contains 'N' space-separated integers that represent the array.
Output:
Output the lexicographically smallest array possible after at most 'K' swaps for each test case.
Constraints:
- 1 <= T <= 100
- 1 <= N <= 5000
- 1 <= K <= 10^9
- 0 <= ARR[i] <= 10^5
Note:
Focus on implementing the function; input and output handling is managed for you.
The task is to determine the lexicographically smallest array that can be obtained by performing at most 'K' swaps of consecutive elements.
Sort the array in non-decreasing order and keep track of the ...read more
Top Paytm Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in Paytm Software Developer
Reviews
Interviews
Salaries
Users/Month