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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n log(m * n)) for sorting operations.
Space Complexity: O(m * n) due for handling the flattened matrix copy.
| Approach | Complexity |
|---|---|
| Greedy Priority Queue Approach | Time Complexity: |
| Two-Pointer Consolidation Strategy | Time Complexity: |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 848,237 views views
Watch 9 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