Problem

Submissions

Hints & solutions

Discuss

Nearly Sorted

Moderate

0/80

Average time to solve is 10m

Contributed by

26 upvotes

Asked in companies

Problem statement

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 ( Input/output format, Notes, Images )

Input Format:

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.

Output Format:

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

Note :

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

Constraints:

1 <= T <= 100
1 <= K < N <= 5000
1 <= ARR[i] <= 10^9 

Time Limit: 1 sec

Sample Input 1:

1
7 3 
6 5 3 2 8 10 9

Sample Output 1:

2 3 5 6 8 9 10

Explanation For Sample Input 1:

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.

Sample Input 2:

1
8 4
10 9 8 7 4 70 60 50

Sample Output 2:

4 7 8 9 10 50 60 70

Explanation For Sample Input 2:

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.

Hint 1

Hint 2

Think of a sorting algorithm which can be used here.

Approaches (2)

Approach 1

Approach 2

Sorting Algorithms Based Approach

We will use the Insertion sort to sort the elements efficiently. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands, where we do the following steps.

Iterate the array from array[1] to array[n] over the array, where n is the size of the array.
Compare the current element (key) to its predecessor.
If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Time Complexity

O(N*K), where N is the number of elements in the array and K is the maximum deviation of an element from it’s target position.

In the worst case, to move every element to its correct place, at most K elements need to be moved.

Space Complexity

O(N), where N is the number of elements in the array.

As we are using an array of size N.

(100% EXP penalty)

Nearly Sorted

Console