Watch 9 video solutions for Maximum Spending After Buying Items, a hard level problem involving Array, Greedy, Sorting. This walkthrough by Joyjit Codes has 205 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed m * n integer matrix values, representing the values of m * n different items in m different shops. Each shop has n items where the jth item in the ith shop has a value of values[i][j]. Additionally, the items in the ith shop are sorted in non-increasing order of value. That is, values[i][j] >= values[i][j + 1] for all 0 <= j < n - 1.
On each day, you would like to buy a single item from one of the shops. Specifically, On the dth day you can:
i.j for the price of values[i][j] * d. That is, find the greatest index j such that item j was never bought before, and buy it for the price of values[i][j] * d.Note that all items are pairwise different. For example, if you have bought item 0 from shop 1, you can still buy item 0 from any other shop.
Return the maximum amount of money that can be spent on buying all m * n products.
Example 1:
Input: values = [[8,5,2],[6,4,1],[9,7,3]] Output: 285 Explanation: On the first day, we buy product 2 from shop 1 for a price of values[1][2] * 1 = 1. On the second day, we buy product 2 from shop 0 for a price of values[0][2] * 2 = 4. On the third day, we buy product 2 from shop 2 for a price of values[2][2] * 3 = 9. On the fourth day, we buy product 1 from shop 1 for a price of values[1][1] * 4 = 16. On the fifth day, we buy product 1 from shop 0 for a price of values[0][1] * 5 = 25. On the sixth day, we buy product 0 from shop 1 for a price of values[1][0] * 6 = 36. On the seventh day, we buy product 1 from shop 2 for a price of values[2][1] * 7 = 49. On the eighth day, we buy product 0 from shop 0 for a price of values[0][0] * 8 = 64. On the ninth day, we buy product 0 from shop 2 for a price of values[2][0] * 9 = 81. Hence, our total spending is equal to 285. It can be shown that 285 is the maximum amount of money that can be spent buying all m * n products.
Example 2:
Input: values = [[10,8,6,4,2],[9,7,5,3,2]] Output: 386 Explanation: On the first day, we buy product 4 from shop 0 for a price of values[0][4] * 1 = 2. On the second day, we buy product 4 from shop 1 for a price of values[1][4] * 2 = 4. On the third day, we buy product 3 from shop 1 for a price of values[1][3] * 3 = 9. On the fourth day, we buy product 3 from shop 0 for a price of values[0][3] * 4 = 16. On the fifth day, we buy product 2 from shop 1 for a price of values[1][2] * 5 = 25. On the sixth day, we buy product 2 from shop 0 for a price of values[0][2] * 6 = 36. On the seventh day, we buy product 1 from shop 1 for a price of values[1][1] * 7 = 49. On the eighth day, we buy product 1 from shop 0 for a price of values[0][1] * 8 = 64 On the ninth day, we buy product 0 from shop 1 for a price of values[1][0] * 9 = 81. On the tenth day, we buy product 0 from shop 0 for a price of values[0][0] * 10 = 100. Hence, our total spending is equal to 386. It can be shown that 386 is the maximum amount of money that can be spent buying all m * n products.
Constraints:
1 <= m == values.length <= 101 <= n == values[i].length <= 1041 <= values[i][j] <= 106values[i] are sorted in non-increasing order.Problem Overview: You are given a matrix where each row represents items in a shop and prices decrease from left to right. You must buy exactly one item per day. The amount spent for an item equals price * day. Since the day multiplier increases over time, the goal is to schedule purchases so that cheaper items are bought earlier and expensive ones later, maximizing the final total spending.
Approach 1: Greedy Priority Queue (Min Heap) (Time: O(mn log m), Space: O(m))
The key constraint is that items in each row must be bought from right to left. The rightmost value of every row is therefore the next available (and cheapest) item from that shop. Push these candidates into a min-heap. Each day, extract the smallest price across all rows and add price * day to the total. After removing an item from row r, move the pointer one step left and push the next available item from that row into the heap. This greedy rule works because buying the smallest available price earlier maximizes the multiplier effect for larger prices later. Heap operations keep selection efficient while respecting the perârow order constraint. This method directly combines greedy reasoning with a priority queue to always pick the globally cheapest valid item.
Approach 2: Two-Pointer Consolidation Strategy (Time: O(mn log(mn)), Space: O(mn))
Another way to think about the problem is that every item will eventually be purchased; only the order matters. Because each row is already sorted in decreasing order, the rightmost elements are always the smallest in their row. If you flatten the entire matrix into a single list and apply sorting in ascending order, the resulting order naturally respects the per-row constraint: cheaper elements (which appear toward the right of rows) appear earlier in the sorted sequence. Once sorted, assign purchase days sequentially using two pointers or an indexâmultiply the smallest price by day 1, the next by day 2, and so on. This approach is simple to implement and avoids heap operations, but sorting all m * n elements increases both time and memory usage compared with the heap-based greedy method.
Recommended for interviews: The greedy minâheap solution is what most interviewers expect. It shows you recognized the scheduling insight (buy cheap items early) and handled the row ordering constraint efficiently with a heap. A full flatten-and-sort approach still demonstrates understanding of the greedy ordering idea, but the heap method is more optimal in space and typically discussed in strong solutions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Priority Queue (Min Heap) | O(mn log m) | O(m) | Best general solution when rows must be consumed rightâtoâleft and you want efficient global minimum selection |
| Two-Pointer Consolidation with Sorting | O(mn log(mn)) | O(mn) | Simpler implementation when memory is not constrained and flattening the matrix is acceptable |