Shelf Total After Orders

Medium

Items stand in a row on a shelf, and prices[i] is the price of the item at index i. Orders arrive in orders, each one a pair [index, k], and they are processed strictly in order: 1. If the item at index is still on the shelf, it is taken. 2. Then the k cheapest remaining items are taken. On equal prices, the item with the smaller index goes first. If fewer than k items are left, all of them are taken. Return a list holding, after each order, the total price of the items still on the shelf.

Example 1

prices=[4, 1, 3, 1, 5], orders=[[2, 1], [4, 2]] → [10, 0]

The first order takes the item at index 2 (price 3) plus the single cheapest one, the 1 at index 1. What remains is 4 + 1 + 5 = 10. The second order takes item 4 (price 5) and the two cheapest left, 1 and 4. The shelf is empty, so the total is 0.

Example 2

prices=[2, 7, 2, 9], orders=[[3, 0], [3, 1]] → [11, 9]

The first order takes only item 3, leaving 2 + 7 + 2 = 11. In the second, item 3 is already gone, and of the two 2s the one with the smaller index (index 0) is taken, leaving 7 + 2 = 9.

Example 3

prices=[6], orders=[[0, 0]] → [0]

Constraints

1 ≤ len(orders) ≤ len(prices) ≤ 10⁵
1 ≤ prices[i] ≤ 10⁵
orders[i] = [index, k], 0 ≤ index, k ≤ len(prices) − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Sorting Simulation Heap (Priority Queue)