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:

- We will create a min-heap which have a minimum value at its roots.
- 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. - 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*. - At each iteration of the loop, we increment the index variable with +1 and loop variable with +1.
- 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.