All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Decode The Code

Greedy Algorithms


Mr. Seth and his friend are on a secret mission to infiltrate the terrorist organization. He has to pass the last security point by entering N digit passcode. His friend has successfully got the digits of the passcode but they are not in the correct order. In his college time, he was taught Automata by a brilliant professor at his college. So, he decided to design a machine that can arrange the digits correctly to unlock the last point. It was known to Mr. Seth that the correct passcode is the lexicographically the largest combination of these digits. Now the machine can only swap K adjacent digits.

Mr. Seth does not have much time, so he requires your help to operate the machine correctly.


  • The first line of input contains an integer T denoting the number of test cases.
  • Each test case contains two lines, the first line contains two integers N and K. Where N is the number of digits and K denotes swaps allowed.
  • Second-line contains N space-separated digits ai.


Print lexicographically largest combination of digits for each test case separated in a new line.


  • 1 <= T  <=100
  • 1 <= N <= 105
  • 0 <= ai <= 9
  • 1 <= k <= n

Note: Use fast i/o to handle large test cases.

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

In the first test case:
The first swap is between 3 and 5. Second swap between 1 and 2.
In the second test case:
The first swap between 1 and 2 and the passcode will look like: 3 2 1 1 2
The second swap between 1 and 2 and the passcode will be: 3 2 1 2 1
The third swap is between 1 and 2 and the passcode will be: 3 2 2 1 1.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications