Loading...
Loading...
Loading...
Priya links k bank accounts to her UPI app. Each account sends its transactions as a list of amounts in paise, already sorted from small to large. A negative amount is money going out.
Some accounts had no transactions, so their list is empty. Merge all the lists into one list sorted from small to large and print it. Equal amounts stay as separate entries.
0.Example 1
Input
3 3 1 4 9 2 2 8 4 3 3 5 10
Output
1 2 3 3 4 5 8 9 10
Three lists of lengths 3, 2 and 4 merge into one list of 9 amounts.
Example 2
Input
3 0 2 -500 700 1 -500
Output
-500 -500 700
The first account is empty. The two -500 amounts both stay.
Try the problem first. Open one hint at a time.
The smallest amount overall must be the first amount of one of the lists.
Keep one "front" amount from each non-empty list in a min-heap, together with which list it came from and its position.
Take the smallest front out, print it, and put the next amount of that same list into the heap.
Compare amounts with Integer.compare, not by subtracting them. The difference can be bigger than an int holds.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor