PROBLEM LINK:
Author: Yogesh Malpani
Editorialist: Yogesh Malpani
DIFFICULTY:
MEDIUM.
PREREQUISITES:
ArrayList, Binary Search, Heap
PROBLEM:
Given the values of N transactions, the task is to insert these to records and print the value of Kth highest transaction in the records at each insertion.
QUICK EXPLANATION:
Find the index for the each new transaction using efficient Sorting algorithms which work well on an almost sorted list.
Next find the Kth highest transaction and print it.
EXPLANATION:
How to process a new transaction of record, Ni?
For every Ni, check if it is smaller than current Kth largest element.
If yes, then ignore it. If no, then a modification of Binary Search can be used to find the index for the Ni. This can be done in O(LogN) time.
The transaction value is added at an index in the ArrayList which runs in amortized constant time, O(N) time.
So the Time complexity of processing a new transaction is O(N + LogN).
The Kth highest transaction is found in the ArrayList in constant time, O(1).
ALTERNATIVE SOLUTION:
Another Solution is to use Min Heap of size N to store N largest transactions of records. The Kth highest transaction is always at root and can be found in O(1) time.
How to process a new transaction of record?
Compare the new transaction value, Ni, with root of heap. If Ni is smaller, then ignore it. Otherwise replace root with Ni and call heapify for the root of modified heap. Time complexity of finding the Kth highest transaction is O(LogN).
AUTHOR’S SOLUTION:
Solution can be found here.