Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You’re given an array/list 'ARR' of N elements, where each element is at most K away from its target position(Position if the array was sorted). Now, your task is to devise an algorithm that sorts the given array in O(N log K) time.

For example:

```
Let us consider 'K' is 3, an element at index 4 in the sorted array, can be at indexes 1, 2, 3, 4, 5, 6, 7 in the given array, because the absolute difference of all these indices with 4 is at most 3.
```

Detailed explanation

```
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and K, the number of elements in the array and K as specified in the problem statement.
The second line of each test contains N space-separated integers.
```

```
The only line of output of each test case should contain N space-separated integers denoting the sorted array.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= K < N <= 5000
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
```

```
1
7 3
6 5 3 2 8 10 9
```

```
2 3 5 6 8 9 10
```

```
We could move 6 from position 1 to as far as position 4 (as K=4) and we moved it to position 4 and it can be seen that after that all elements to the left(i.e position 1 to 3) are less than 6, hence 10 is at its best position now. Similarly, we do this for all the elements, to reach our answer.
```

```
1
8 4
10 9 8 7 4 70 60 50
```

```
4 7 8 9 10 50 60 70
```

```
We could move 10 from position 1 to as far as position 5(as K=4) and we moved it to position 5 and it can be seen that after that all elements to the left(i.e position 1 to 4) are less than 10, hence 10 is at its best position now. Similarly we do this for all the elements, to reach our answer.
```