Skip to main content
Talentd

Maximum Spending After Buying Items - Solution & Explanation

HardArrayGreedySortingHeap (Priority Queue)24 min readAsked at: Tiktok, Zomato
Practice this problem

Problem Statement

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 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 <= 10
  • 1 <= n == values[i].length <= 104
  • 1 <= values[i][j] <= 106
  • values[i] are sorted in non-increasing order.

Approach Overview

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 1: Greedy Priority Queue Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Two-Pointer Consolidation Strategy

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n log(m * n)) for sorting operations.
Space Complexity: O(m * n) due for handling the flattened matrix copy.

Try this approach in the editor →

Approach 3: Greedy + Priority Queue

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Priority Queue Approach

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.

Two-Pointer Consolidation Strategy

Time Complexity: O(m * n log(m * n)) for sorting operations.
Space Complexity: O(m * n) due for handling the flattened matrix copy.

Greedy + Priority Queue—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 SortingO(mn log(mn))O(mn)Simpler implementation when memory is not constrained and flattening the matrix is acceptable

Video Solution

Maximum Spending After Buying Items - LEETCODE BIWEEKLY CONTEST 117 • Joyjit Codes • 205 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Spending After Buying Items easy or hard?
The problem is classified as Hard because it combines greedy reasoning with constraints on matrix ordering. Recognizing that cheaper items must be bought earlier and implementing that efficiently with a heap is the main challenge.
Maximum Spending After Buying Items Python/Java solution
Most implementations follow the same heap pattern. In Python, use heapq with tuples storing (price, row, col). In Java, use a PriorityQueue with a comparator on price. Each pop updates the total spending and pushes the next element from that row.
How to solve Maximum Spending After Buying Items in O(mn log m)?
Use a greedy priority queue. Push the cheapest available item from each row (the rightmost column) into a min‑heap. Each day, pop the smallest price, add price × day to the total, and push the next item from that same row. This guarantees cheaper items are purchased earlier while maintaining row ordering.
What is the best approach for Maximum Spending After Buying Items?
The most efficient approach is a greedy min‑heap strategy. Insert the rightmost (currently cheapest) item from each row into a priority queue, repeatedly extract the minimum price, and multiply it by the current day. After removing an item, push the next item from that row. This runs in O(mn log m) time and O(m) space.
Is Maximum Spending After Buying Items asked at Google/Amazon/Meta?
Problems combining greedy scheduling with heaps and matrix traversal frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving priority queues and optimal ordering are common in senior algorithm rounds.
What data structure is used in Maximum Spending After Buying Items?
The key data structure is a min‑heap (priority queue) that tracks the cheapest currently available item across rows. Arrays or matrix indexing track the current column pointer for each row as items are consumed from right to left.
What is the time complexity of Maximum Spending After Buying Items?
The optimal heap-based solution runs in O(mn log m) time where m is the number of rows and n is the number of columns. Each of the mn items is pushed and popped from a heap of size at most m. Space complexity is O(m) for storing row candidates.

Ready to solve this problem?

Practice Maximum Spending After Buying Items with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Points You Can Obtain from Cards

Next

Maximum Score from Performing Multiplication Operations