Loading page…
Practice problem · easy
An online store lists many sellers' offers for the same product. The product page shows only the k cheapest prices, with the cheapest first.
A popular product can have up to 100,000 offers, and k is usually small, such as 5 or 10. The page must load fast, so the code should not sort every offer only to show a few.
Write cheapest_offers(prices, k).
prices[i] is the price of offer i.k lowest prices, cheapest first. Equal prices count separately.k is never larger than the number of offers.Input: prices = [40, 15, 60, 25, 10, 30], k = 3
Output: [10, 15, 25]| New price | The 3 cheapest so far | Dropped |
|---|---|---|
| 40 | 40 | |
| 15 | 15, 40 | |
| 60 | 15, 40, 60 | |
| 25 | 15, 25, 40 | 60 |
| 10 | 10, 15, 25 | 40 |
| 30 | 10, 15, 25 | 30 |
Whenever the heap holds more than 3 prices, the dearest leaves. The three that stay, cheapest first, are 10, 15 and 25.
Input: prices = [5, 5, 5], k = 2
Output: [5, 5]All three offers cost the same. Two of them are the answer, so the list is 5, 5.
Input: prices = [9, 2], k = 2
Output: [2, 9]Every offer is shown, and the list is sorted cheapest first.
1 ≤ length of prices ≤ 10^51 ≤ prices[i] ≤ 10^61 ≤ k ≤ length of pricesScanning the list once is fine: 100,000 steps. Scanning it k times is fine for a small k, but k can be as large as the whole list, and then the scans cost about n squared.
A heap of size k handles every k: each price costs about log k steps, so the whole list costs n log k.
cheapest_offers · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.