Home » Interview coding problems/challenges

Sort K-Sorted Array

Sort K-Sorted Array: You are given an array of n elements such that each element is at max k place away from its original sorted position, you have to sort the array in correct manner.
Submitted by Divyansh Jaipuriyar, on August 27, 2020

Problem statement

You are given an array of n elements such that each element is at max k place away from its original sorted position, you have to sort the array in the correct manner.

Problem description:

The problem asks you to sort the array in minimum possible time, the main catch here is how to use the information that the elements are at maximum k place away from its original sorted position.

Input

The first line of the input consists of T number of test cases, each test case consists of N size of the array following line consist of N numbers as the input of the array.

Output

You are required to print the sorted form of the array.

Examples:

Input:
T=1
N=4 2
3 1 2 4

Output:
1 2 3 4
Since 3 original position is at index 0 
but in the sorted array it should be at index 2, 1 should be 
at index 0 and 2 should bet at index 1 therefore maximum distance 
between the current position and sorted position is 2 
therefore it can be solved with the help of heap.

Input:
T=1
N=6 K=4
4 3 2 1 5 6

Output:
1 2 3 4 5 6
Similarly, as the previous case the maximum difference between 
original index and current position is 3 for element 4 indexed at 0.

Solution Approach

The problem asks you to solve it in an efficient manner since it is possible to sort the array with the help of insertion sort method which will take O(n*k) time since we have a total of a number of elements and each element can be at max k place away from its original position. So to avoid that time complexity we will use the heap data structure:

1. We will create a min-heap which have a minimum value at its roots.
2. The size of the heap should be (k+1) as at any moment we store k+1 elements into the min-heap and remove root element and store it in array at the correct position with the help of some index variable.
3. At first, we store k+1 elements into the heap and initialize the index variable with 0 and the loop variable with the current index that is k.
4. At each iteration of the loop, we increment the index variable with +1 and loop variable with +1.
5. At last, when all iteration is completed with the loop we if we still have few elements left in the heap then we pop it and store it into the given array.

The overall time complexity for the above approach in the worst case is: O(nlog(k))

Space complexity for the above approach in worst case i: O(k+1)

C++ Implementation (Heap Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter N and K: ";
        ll n, k;
        cin >> n >> k;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //declare priority queue(min heap)
        priority_queue<ll, vector<ll>, greater<ll> > pq;

        //push k+1 first element of the array
        //into the priority queue.
        for (ll i = 0; i <= k; i++)
            pq.push(arr[i]);

        //declare index variable with 0.
        ll index = 0;

        //iterate through rest elements and
        //store k+1 elements into the heap.
        //during each iteration.
        for (ll i = k + 1; i < n; i++) {
            arr[index] = pq.top();
            pq.pop();
            pq.push(arr[i]);
            index++;
        }

        //store elements in correct position
        //till heap is empty.
        while (!pq.empty()) {
            arr[index] = pq.top();
            pq.pop();
            index++;
        }

        cout << "Final array: ";
        for (ll i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter N and K: 4 2
Enter array elements: 3 1 2 4
Final array: 1 2 3 4 
Enter N and K: 10 2
Enter array elements: 1 4 5 2 3 7 8 6 10 9
Final array: 1 2 3 4 5 6 7 8 9 10 
Enter N and K: 6 4
Enter array elements: 4 3 2 1 5 6
Final array: 1 2 3 4 5 6