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.
The idea is to treat each item in the matrix and consider its value alongside the potential day (multiplier) it will be bought. Start from the maximum number of days, and always buy the most expensive available item by leveraging a priority queue (max-heap) to fetch the highest value items efficiently.
The solution uses a greedy approach to maximize spending. All items across all shops are added to a single list. These items are sorted by value in descending order using qsort. For each subsequent purchase day, the optimal item (greatest value) is fetched from this list, and is bought with the current day's multiplier. The result is the maximal total spending where the largest item values are prioritized for the latest (highest-multiplier) days.
Time Complexity: O(m * n log(m * n)) due to sorting the items list.
Space Complexity: O(m * n) for storing all items in a flattened array.
This strategy leverages two pointers to simultaneously track the lowest and highest-value items across all available items on each day. By interleaving these pointers and maximizing increments based on potential payouts, the methodology ensures maximized total payouts by sifting through available items selectively.
This variant treats all items as a singular flat list, sorting this list to prioritize expensive purchases on future days with greater multipliers. Here, by flattening and sorting items by value in descending priority, the single-pass iteration multiplies descending indexed values with ascending day indices, maximizing potential spending.
Time Complexity: O(m * n log(m * n)) for sorting operations.
Space Complexity: O(m * n) due for handling the flattened matrix copy.
According to the problem description, we should prioritize purchasing items with smaller values and leave items with larger values to be purchased later in order to maximize the total cost. Therefore, we use a priority queue (min-heap) to store the smallest value item that has not been purchased in each store. Initially, we add the rightmost item in each store to the priority queue.
Each day, we take out the item with the smallest value from the priority queue, add it to the answer, and add the previous item in the store where the item is located to the priority queue. We repeat the above operation until the priority queue is empty.
The time complexity is O(m times n times log m), and the space complexity is O(m). Here, m and n are the number of rows and columns of the array values, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Priority Queue Approach | Time Complexity: |
| Two-Pointer Consolidation Strategy | Time Complexity: |
| Greedy + Priority Queue | — |
| 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 |
Maximum Spending After Buying Items - LEETCODE BIWEEKLY CONTEST 117 • Joyjit Codes • 205 views views
Watch 8 more video solutions →Practice Maximum Spending After Buying Items with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor