Loading page…
Practice problem · medium
An online store's cart page shows a banner: "Cheapest item in your cart". A shopper can add an item, or press Undo. Undo removes the item that was added most recently and is still in the cart.
Each action is a number. A positive number is the price of an item being added, in minor units. A 0 is Undo, and Undo on an empty cart does nothing.
The banner must update after every action. A long session can hold up to 100,000 actions.
Write cheapest_after_each(actions).
actions is a list of whole numbers. A positive number adds an item with that price. 0 presses Undo.-1 when the cart is empty.Input: actions = [5, 3, 8, 0, 0, 4]
Output: [5, 3, 3, 3, 5, 4]| Step | Action | Cart after (oldest first) | Cheapest after |
|---|---|---|---|
| 1 | add 5 | 5 | 5 |
| 2 | add 3 | 5, 3 | 3 |
| 3 | add 8 | 5, 3, 8 | 3 |
| 4 | Undo: removes 8 | 5, 3 | 3 |
| 5 | Undo: removes 3 | 5 | 5 |
| 6 | add 4 | 5, 4 | 4 |
After step 5 the cheapest item is gone, so the answer returns to 5. A single running minimum could not know that.
Input: actions = [0, 7]
Output: [-1, 7]Undo on an empty cart changes nothing, and the banner stays at -1.
Input: actions = [2, 2, 0, 0, 0]
Output: [2, 2, 2, -1, -1]Two items cost the same. Each Undo removes one of them, and the third Undo finds an empty cart.
1 ≤ number of actions ≤ 10^50 ≤ each action ≤ 10^6A plan that scans the whole cart after every action costs up to n^2 / 2 comparisons: 5 × 10^9 when 50,000 items sit in the cart. That is too slow.
So each action must take a constant number of steps. The answer after an Undo must come back without scanning, which means it was saved when the item was added.
cheapest_after_each · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.