Maximum Spending After Buying Items
HardPrompt
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:
- Pick any shop
i. - Buy the rightmost available item
jfor the price ofvalues[i][j] * d. That is, find the greatest indexjsuch that itemjwas never bought before, and buy it for the price ofvalues[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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward approach based on the greedy strategy. The core idea is that to maximize the total spending, we must pair the smallest item values with the smallest day numbers (1, 2, 3, ...) and the largest item values with the largest day numbers (..., mn-1, mn). This is a direct application of the rearrangement inequality. The algorithm first collects all m * n item values from the 2D matrix into a single 1D list, then sorts this list in ascending order. Finally, it iterates through the sorted list, multiplying the i-th value (1-indexed) with the day number i and summing up the results to get the maximum possible spending.
Algorithm
- Create a new 1D list, say
allItems, of sizem * n. - Iterate through the
valuesmatrix (fromi=0tom-1,j=0ton-1). - Copy each
values[i][j]into theallItemslist. - Sort the
allItemslist in ascending order. - Initialize
totalSpending = 0andday = 1. - Iterate through the sorted
allItemslist. For eachvalue:totalSpending += value * dayday++
- Return
totalSpending.
Walkthrough
The algorithm begins by creating a one-dimensional list to hold all m * n item values. It then iterates through each row and column of the input values matrix, adding every item's value to this new list. Once all values are collected, the list is sorted in non-decreasing order. This ensures that the items are ordered from cheapest to most expensive. A variable totalSpending is initialized to zero. Another variable day is initialized to 1. The algorithm then iterates through the sorted list. For each value v at index i (0-indexed), it calculates the cost for day i+1 as v * (i+1). This product is added to totalSpending. After iterating through all the values, totalSpending holds the maximum possible amount, which is returned. The logic is sound because the buying constraints allow us to pick the globally cheapest available item on any given day. By sorting all values, we are essentially simulating this process: on day 1 we buy the cheapest of all items, on day 2 the second cheapest, and so on.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public long maxSpending(int[][] values) { int m = values.length; int n = values[0].length; List<Integer> allItems = new ArrayList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { allItems.add(values[i][j]); } } Collections.sort(allItems); long totalSpending = 0; long day = 1; for (int value : allItems) { totalSpending += (long) value * day; day++; } return totalSpending; }}Complexity
Time
O((m*n) * log(m*n)). Flattening takes O(m*n). Sorting `m*n` elements takes O((m*n) * log(m*n)). The final summation takes O(m*n). The dominant part is sorting.
Space
O(m*n). We need an auxiliary list to store all `m*n` items.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem based on the greedy principle.
Cons
High space complexity, as it requires storing all
m*nitems in a separate list. This can be memory-intensive for largemandn.Time complexity is not optimal, as it involves sorting a large list and doesn't leverage the pre-sorted nature of the rows in the input matrix.
This approach improves upon the space complexity of the first one by avoiding the creation of a large intermediate list. It simulates the day-by-day buying process directly. On each day, from 1 to m*n, we need to buy the cheapest item currently available. The cheapest available item in any shop i is the rightmost one that hasn't been bought yet. This approach keeps track of the index of the next item to be bought from each shop. In each step (day), it scans through all m shops to find the one with the minimum-valued available item, "buys" it, and updates the index for that shop.
Algorithm
- Initialize an array
itemIndicesof sizemwith all valuesn-1. - Initialize
totalSpending = 0L. - Loop
dayfrom 1 tom*n.- Initialize
minVal = infinityandshopWithMin = -1. - Iterate
ifrom 0 tom-1.- If shop
ihas items left (itemIndices[i] >= 0) andvalues[i][itemIndices[i]] < minVal:- Update
minVal = values[i][itemIndices[i]]. - Update
shopWithMin = i.
- Update
- If shop
- Add
(long)minVal * daytototalSpending. - Decrement
itemIndices[shopWithMin].
- Initialize
- Return
totalSpending.
Walkthrough
We maintain an array of pointers, say itemIndices, of size m. itemIndices[i] stores the index of the rightmost (cheapest) available item in shop i. Initially, all pointers are set to n-1. We loop for m*n days. In each iteration d (from 1 to m*n): we search for the overall cheapest item among the currently available items from all shops. We iterate from shop 0 to m-1. We keep track of the minimum value found so far (minVal) and the shop it belongs to (shopWithMin). For each shop i, if it still has items left (i.e., itemIndices[i] >= 0), we compare values[i][itemIndices[i]] with minVal. If it's smaller, we update minVal and shopWithMin. After checking all shops, minVal will be the value of the item to buy on day d. We add minVal * d to our totalSpending. We then "buy" this item by decrementing the pointer for the corresponding shop: itemIndices[shopWithMin]--. This process is repeated until all items are bought.
import java.util.Arrays; class Solution { public long maxSpending(int[][] values) { int m = values.length; int n = values[0].length; int[] itemIndices = new int[m]; Arrays.fill(itemIndices, n - 1); long totalSpending = 0; for (long day = 1; day <= m * n; day++) { int minVal = Integer.MAX_VALUE; int shopWithMin = -1; for (int i = 0; i < m; i++) { if (itemIndices[i] >= 0) { if (values[i][itemIndices[i]] < minVal) { minVal = values[i][itemIndices[i]]; shopWithMin = i; } } } totalSpending += (long) minVal * day; if (shopWithMin != -1) { itemIndices[shopWithMin]--; } } return totalSpending; }}Complexity
Time
O(m^2 * n). The outer loop runs `m*n` times. Inside, we iterate through `m` shops to find the minimum. This results in `(m*n) * m` operations.
Space
O(m). We only need an array of size `m` to keep track of the indices for each shop.
Trade-offs
Pros
Excellent space complexity, much better than the flatten-and-sort approach.
Does not require modifying the input or creating large data structures.
For the given constraints where
mis small, this can be faster than the flatten-and-sort approach.
Cons
The time complexity is quadratic in
m, which would be inefficient ifmwere large.Repeatedly scanning all
mshops to find the minimum is inefficient. A better data structure can optimize this search.
This is the most efficient approach. It recognizes the problem as a classic "merge k sorted lists" problem, where k is the number of shops m. Each shop's items, when read from right to left, form a sorted list (non-decreasing values). We can use a min-heap to efficiently find the minimum element among the m available items at any point in time.
Algorithm
- Create a min-heap that compares elements based on their value.
- For each shop
ifrom 0 tom-1, add the tuple(values[i][n-1], i, n-1)to the heap. - Initialize
totalSpending = 0Landday = 1L. - While the heap is not empty:
- Extract the minimum element
(value, shop_idx, item_idx)from the heap. - Add
(long)value * daytototalSpending. - Increment
day. - If
item_idx > 0, add the next item from the same shop,(values[shop_idx][item_idx-1], shop_idx, item_idx-1), to the heap.
- Extract the minimum element
- Return
totalSpending.
Walkthrough
The algorithm uses a min-heap to keep track of the cheapest available item from each of the m shops. The heap stores elements representing an item, for example, as an array [value, shop_index, item_index]. The heap is ordered by value. Initially, the heap is populated with the cheapest item from each shop, which is the rightmost item values[i][n-1] for each shop i. So, we add [values[i][n-1], i, n-1] for all i from 0 to m-1 into the min-heap. Then, we loop m*n times, corresponding to the days. In each iteration d: we extract the minimum element from the heap. This element, say [value, shop_idx, item_idx], represents the globally cheapest item available. We calculate the spending for the current day as value * d and add it to the totalSpending. Since we've "bought" the item from shop_idx at item_idx, we need to add the next cheapest item from that same shop to the heap. This would be the item at item_idx - 1. If shop_idx has more items left (i.e., item_idx - 1 >= 0), we add the new item [values[shop_idx][item_idx - 1], shop_idx, item_idx - 1] to the heap. This process ensures that on each day, we are always picking the absolute cheapest item available among all shops, and we do it efficiently using the heap property.
import java.util.PriorityQueue; class Solution { public long maxSpending(int[][] values) { int m = values.length; int n = values[0].length; // Min-heap to store [value, shop_index, item_index] PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Initialize the heap with the last item from each shop for (int i = 0; i < m; i++) { minHeap.offer(new int[]{values[i][n - 1], i, n - 1}); } long totalSpending = 0; long day = 1; while (!minHeap.isEmpty()) { int[] current = minHeap.poll(); int value = current[0]; int shopIdx = current[1]; int itemIdx = current[2]; totalSpending += (long) value * day; day++; // If there are more items in the same shop, add the next one to the heap if (itemIdx > 0) { int nextItemIdx = itemIdx - 1; int nextValue = values[shopIdx][nextItemIdx]; minHeap.offer(new int[]{nextValue, shopIdx, nextItemIdx}); } } return totalSpending; }}Complexity
Time
O((m*n) * log(m)). Initializing the heap takes O(m log m). The loop runs `m*n` times. Each iteration involves one `poll` and at most one `offer`, both taking O(log m) time. Thus, the total time is O(m log m + (m*n) log m) which simplifies to O((m*n) log m).
Space
O(m). The heap stores at most one item from each of the `m` shops.
Trade-offs
Pros
Most efficient approach in terms of both time and space complexity.
Effectively utilizes the sorted property of the input rows.
Scales well even if
mwere larger.
Cons
Slightly more complex to implement than the other approaches due to the use of a priority queue.
Solutions
Solution
class Solution {public long maxSpending(int[][] values) { int m = values.length, n = values[0].length; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]); for (int i = 0; i < m; ++i) { pq.offer(new int[]{values[i][n - 1], i, n - 1}); } long ans = 0; for (int d = 1; !pq.isEmpty(); ++d) { var p = pq.poll(); int v = p[0], i = p[1], j = p[2]; ans += (long)v * d; if (j > 0) { pq.offer(new int[]{values[i][j - 1], i, j - 1}); } } return ans; }}class Solution {public: long long maxSpending(vector<vector<int>> &values) { priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; int m = values.size(), n = values[0].size(); for (int i = 0; i < m; ++i) { pq.emplace(values[i][n - 1], i, n - 1); } long long ans = 0; for (int d = 1; pq.size(); ++d) { auto [v, i, j] = pq.top(); pq.pop(); ans += 1LL * v * d; if (j) { pq.emplace(values[i][j - 1], i, j - 1); } } return ans; }};class Solution: def maxSpending(self, values: List[List[int]]) -> int: n = len(values[0]) pq = [(row[- 1], i, n - 1) for i, row in enumerate(values)] heapify(pq) ans = d = 0 while pq: d += 1 v, i, j = heappop(pq) ans += v * d if j: heappush(pq, (values[i][j - 1], i, j - 1)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.