I was asked a question in the end of an interview, but didn't solve it within 10-15 minutes.

Question

We have an integer array of n elements from 1-9, which constructs a large integer number, e.g. [2,1,3,4] --> 1234. We can swap any two adjacent elements k times, return the minimum value we can obtain. E.g.:

Input: [3,1,4,2], n = 4

Result:
k = 1:   [1,3,4,2]
k = 2:   [1,3,2,4]
k = 10:  [1,2,3,4]

A NlogN solution is required.

My thought

Sort the array elements, and try to move the smallest element to the begining whenever we have enough times to swap, but this is definitely not NlogN, and I failed the interview. Unfortunately up to now, I still have no idea how to solve this problem in that time complexity..
I hope someone can help me with it.