Thanks for your solution. I didn't use the sorting method because of its time complexity. After implementing the 1st solution, interviewer asked me to do it in-place without using any extra space. And we don't have to keep the order. That was my mistake. I wrote it by mistake in the article, that's why other commenter got misunderstood the problem statement.

I didn't get any response after this interview. Because there were two questions and for the 2nd question I was able to create the approach, but the time was over.

You are given an array of integers and value k. Values in the array are displaced by up to k position. Return the sorted array in most optimal way.

Example:

nums = [20, 30, 10, 40, 60, 50, 100, 80, 70, 90], k = 2

return = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

My answer was in O(nlogk)

I used Heap Data Structure creating a heap of size k and after each pass I removed the minimum element from the heap and stored it into the result array and after that added the next element into the heap. Repeat this process until all the elements are not sorted. So the time complexity becomes O(nlogk) because it takes logk to add an element into a heap size of k and there were n elements