Sort A K Sorted Array - Investigating Applications of Min/Max Heaps
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program which takes as input a very long sequence of numbers and prints the numbers in sorted order. Each number is at most k away from its correctly sorted position. (Such an array is sometimes referred to as being k-sorted).
Pramp: https://www.pramp.com
Examples:
Input:
[ 3, -1, 2, 6, 4, 5 , 8 ]
k = 2
Each number is no more than 2 indices from its final sorted position.
Output:
[ -1, 2, 3, 4, 5, 6, 8 ]
It is often that data finds itself in an almost sorted state.
For example: A server needs to sort orders coming in internationally and due to differences in server loads and network routes some earlier orders come in after later orders.
How do we efficiently sort this almost sorted data?
Whenever I hear or think of sorting or searching, I think of my fast sorting algorithms, binary search, and min/max heaps.
Approach 1 (Brute Force)
Just run a quick sorting algorithm like mergesort or quicksort and have the array sorted in O( n * log(n) ) time.
This is an obvious answer.
The key insight we need to make is that most of the items are very close to their final positions and therefore we need to just “touch up” the order of the items.
How will we perform this “touch up”?
Approach 2 (Min Heap To The Rescue)
Example:
[ 3, -1, 2, 6, 4, 5, 8 ]
k = 2
How do I know who belongs at index 0?
Well, this leads me to ask you, what are the potentialities for each index? What items could be at index 0?
3 can, -1 can (if it moves 1 spot back), 2 can (if it moves 2 spots back), but 6 cannot (it would have to move 3 spots back but k = 2, this is not allowed).
Now our interest is in k + 1 items, 3, -1, and 2 each could go at index 0.
Our job is now reduced to finding the minimum of k + 1 elements at a time.
What data structure helps me with keeping track of minimums and maximums in a set of data very well?
A heap.
We will use a min heap because we want access to the smallest item across k + 1 items.
The Algorithm
Add the first k + 1 items to a min heap.
Iterate through every index in the array.
Place the min item and add the next item that has not been added yet to the heap.
When we cannot add un-added items to the heap near the end (at some point every item will have seen the heap but we will not be at the end of the iteration just yet) we can just continue ejecting and placing the min items.
Complexities
Time: O( n * log( k ) )
For all n items we will perform an insertion and removal from a min heap holding k + 1 items.
Space: O( k )
The heap will hold k + 1 numbers at maximum before an item is ejected.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is 11.3 in the book "Elements of Programming Interviews"
