Maximum Spending After Buying Items solution and explanation
7 more videos on this problem
Maximum Spending After Buying Items - LEETCODE BIWEEKLY CONTEST 117Joyjit Codes · 2:07 · 205 views
2931. Maximum Spending After Buying Items (Leetcode Hard)Programming Live with Larry · 17:15 · 179 views
2931. Maximum Spending After Buying Items | 2 Approaches | BiWeekly 117Tech Courses · 15:37 · 169 views
2931. Maximum Spending After Buying Items || Leetcode || Biweekly Contest 117 SolutionAshish Kumar · 21:16 · 131 views
100043. Maximum Spending After Buying Items : Biweekly Contest 117 : Hard Question SolutionBitByBit - Learn Coding · 0:21 · 97 views
😍 2931. Maximum Spending After Buying ItemsCP Geeks · 10:19 · 77 views
Leetcode 2931. Maximum Spending After Buying Items (heap)LetsCode · 7:21 · 56 views
2931. Maximum Spending After Buying Items. LEETCODE SOLUTIONKorsarOfficial · 13:51 · 10 views
The problem
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.
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.
import heapq
def maxSpending(values):
maxHeap = []
totalDays = sum(len(shop) for shop in values)
for index in range(totalDays):
dayMultiplier = totalDays - index
for shop in values:
if index < len(shop):
heapq.heappush(maxHeap, (-shop[index], dayMultiplier))
maxSpend = 0
while maxHeap:
value, day = heapq.heappop(maxHeap)
maxSpend += (-value) * day
return maxSpend
values1 = [[8,5,2],[6,4,1],[9,7,3]]
print(maxSpending(values1)) # Output: 285
values2 = [[10,8,6,4,2],[9,7,5,3,2]]
print(maxSpending(values2)) # Output: 386import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
static class Item implements Comparable<Item> {
int value;
int dayMultiplier;
Item(int value, int dayMultiplier) {
this.value = value;
this.dayMultiplier = dayMultiplier;
}
public int compareTo(Item o) {
return o.value - this.value;
}
}
public int maxSpending(int[][] values) {
PriorityQueue<Item> maxHeap = new PriorityQueue<>();
int m = values.length;
int n = values[0].length;
int totalDays = m * n;
for (int[] shop : values) {
for (int item : shop) {
maxHeap.add(new Item(item, --totalDays));
}
}
int maxSpend = 0;
while (!maxHeap.isEmpty()) {
Item current = maxHeap.poll();
maxSpend += current.value * ++totalDays;
}
return maxSpend;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] values1 = {{8,5,2},{6,4,1},{9,7,3}};
System.out.println(solution.maxSpending(values1));
int[][] values2 = {{10,8,6,4,2},{9,7,5,3,2}};
System.out.println(solution.maxSpending(values2));
}
}#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
int maxSpending(vector<vector<int>>& values) {
priority_queue<pii, vector<pii>, less<pii>> maxHeap;
int m = values.size();
int n = values[0].size();
int totalDays = m * n;
for (auto& shop : values) {
for (auto& item : shop) {
maxHeap.push({item, n--});
}
}
int maxSpend = 0, day = totalDays;
while (!maxHeap.empty()) {
auto [value, shopIndex] = maxHeap.top(); maxHeap.pop();
maxSpend += value * day--;
}
return maxSpend;
}
int main() {
vector<vector<int>> values1 = {{8,5,2},{6,4,1},{9,7,3}};
cout << maxSpending(values1) << endl;
vector<vector<int>> values2 = {{10,8,6,4,2},{9,7,5,3,2}};
cout << maxSpending(values2) << endl;
return 0;
}class MaxHeap {
constructor() {
this.heap = [];
}
push(element) {
this.heap.push(element);
this.bubbleUp();
}
pop() {
if (this.size() === 0) return null;
if (this.size() === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return top;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index], parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent[0] >= element[0]) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
bubbleDown() {
let index = 0, length = this.heap.length;
while (true) {
let element = this.heap[index];
let leftChildIndex = 2 * index + 1, rightChildIndex = 2 * index + 2;
let leftChild, rightChild, swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild[0] > element[0]) swap = leftChildIndex;
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if ((swap === null && rightChild[0] > element[0]) || (swap !== null && rightChild[0] > leftChild[0]))
swap = rightChildIndex;
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap;
}
}
size() {
return this.heap.length;
}
}
function maxSpending(values) {
const maxHeap = new MaxHeap();
const m = values.length;
const n = values[0].length;
let totalDays = m * n;
for (let shop of values) {
for (let i = 0; i < n; i++) {
maxHeap.push([shop[i], totalDays--]);
}
}
let maxSpend = 0;
while (maxHeap.size()) {
const [value, day] = maxHeap.pop();
maxSpend += value * day;
}
return maxSpend;
}
const values1 = [[8, 5, 2], [6, 4, 1], [9, 7, 3]];
console.log(maxSpending(values1));
const values2 = [[10, 8, 6, 4, 2], [9, 7, 5, 3, 2]];
console.log(maxSpending(values2));#include <stdio.h>
#include <stdlib.h>
typedef struct Item {
int value;
int dayMultiplier;
} Item;
int compareItems(const void* a, const void* b) {
Item* itemA = (Item*)a;
Item* itemB = (Item*)b;
return (itemB->value) - (itemA->value);
}
int maxSpending(int** values, int m, int* n) {
int totalDays = 0;
for (int i = 0; i < m; ++i) totalDays += n[i];
Item* items = (Item*)malloc(sizeof(Item) * totalDays);
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n[i]; ++j) {
items[count].value = values[i][j];
items[count].dayMultiplier = totalDays - j;
count++;
}
}
qsort(items, totalDays, sizeof(Item), compareItems);
int spending = 0;
for (int i = 0; i < totalDays; ++i) {
spending += items[i].value * (m * n[0] - i);
}
free(items);
return spending;
}
int main() {
int values1[][3] = {{8,5,2}, {6,4,1}, {9,7,3}};
int n1[] = {3, 3, 3};
int m1 = 3;
int* v1[m1];
for (int i = 0; i < m1; i++) v1[i] = values1[i];
printf("%d\n", maxSpending(v1, m1, n1));
int values2[][5] = {{10,8,6,4,2}, {9,7,5,3,2}};
int n2[] = {5, 5};
int m2 = 2;
int* v2[m2];
for (int i = 0; i < m2; i++) v2[i] = values2[i];
printf("%d\n", maxSpending(v2, m2, n2));
return 0;
}using System;
using System.Collections.Generic;
class Item : IComparable<Item> {
public int Value { get; set; }
public int DayMultiplier { get; set; }
public int CompareTo(Item other) {
return other.Value.CompareTo(this.Value);
}
}
class Solution {
public int MaxSpending(int[][] values) {
SortedSet<Item> maxHeap = new SortedSet<Item>();
int m = values.Length;
int n = values[0].Length;
int totalDays = m * n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxHeap.Add(new Item { Value = values[i][j], DayMultiplier = totalDays-- });
}
}
int maxSpend = 0;
while (maxHeap.Count > 0) {
var maxItem = maxHeap.Max;
maxHeap.Remove(maxItem);
maxSpend += maxItem.Value * ++totalDays;
}
return maxSpend;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[][] values1 = new int[][] {
new int[] {8, 5, 2},
new int[] {6, 4, 1},
new int[] {9, 7, 3}
};
Console.WriteLine(solution.MaxSpending(values1));
int[][] values2 = new int[][] {
new int[] {10, 8, 6, 4, 2},
new int[] {9, 7, 5, 3, 2}
};
Console.WriteLine(solution.MaxSpending(values2));
}
}This Python solution utilizes heapq which supports heap operations, effectively functioning as a priority queue. Here, values are pushed into the heap. Python supports min-heap naturally, so values are negated to simulate max-heap to optimize higher spending on later days, ensuring that expensive items benefit from hefty multipliers on later purchase days.
Time Complexity: O(m * n log(m * n)) due to heapq operations.
Space Complexity: O(m * n) for the heap storage.
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.
def maxSpending(values):
items = [item for shop in values for item in shop]
items.sort(reverse=True)
maxSpend = sum(items[day] * (day + 1) for day in range(len(items)))
return maxSpend
values1 = [[8,5,2],[6,4,1],[9,7,3]]
print(maxSpending(values1)) # Output: 285
values2 = [[10,8,6,4,2],[9,7,5,3,2]]
print(maxSpending(values2)) # Output: 386import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public int maxSpending(int[][] values) {
List<Integer> items = new ArrayList<>();
int m = values.length, n = values[0].length;
for (int[] shop : values) {
for (int item : shop) {
items.add(item);
}
}
Collections.sort(items, Collections.reverseOrder());
int maxSpend = 0, dayIndex = 1;
for (int value : items) {
maxSpend += value * dayIndex++;
}
return maxSpend;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] values1 = {{8,5,2},{6,4,1},{9,7,3}};
System.out.println(solution.maxSpending(values1));
int[][] values2 = {{10,8,6,4,2},{9,7,5,3,2}};
System.out.println(solution.maxSpending(values2));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSpending(vector<vector<int>>& values) {
vector<int> items;
for (auto& shop : values) {
for (auto item : shop) {
items.push_back(item);
}
}
sort(items.rbegin(), items.rend());
int maxSpend = 0, totalDays = 1;
for (auto value : items) {
maxSpend += value * totalDays++;
}
return maxSpend;
}
int main() {
vector<vector<int>> values1 = {{8,5,2},{6,4,1},{9,7,3}};
cout << maxSpending(values1) << endl;
vector<vector<int>> values2 = {{10,8,6,4,2},{9,7,5,3,2}};
cout << maxSpending(values2) << endl;
return 0;
}function maxSpending(values) {
const items = [];
const m = values.length;
for (const shop of values) {
items.push(...shop);
}
items.sort((a, b) => b - a);
let maxSpend = 0;
for (let day = 0; day < items.length; day++) {
maxSpend += items[day] * (day + 1);
}
return maxSpend;
}
const values1 = [[8, 5, 2], [6, 4, 1], [9, 7, 3]];
console.log(maxSpending(values1)); // Output: 285
const values2 = [[10, 8, 6, 4, 2], [9, 7, 5, 3, 2]];
console.log(maxSpending(values2)); // Output: 386#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)b) - (*(int*)a);
}
int maxSpending(int** values, int m, int n) {
int totalItems = m * n;
int* flatItems = (int*)malloc(sizeof(int) * totalItems);
int index = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
flatItems[index++] = values[i][j];
}
}
qsort(flatItems, totalItems, sizeof(int), compare);
int maxSpend = 0;
for (int day = 1; day <= totalItems; ++day) {
maxSpend += flatItems[day - 1] * day;
}
free(flatItems);
return maxSpend;
}
int main() {
int values1[][3] = {{8,5,2},{6,4,1},{9,7,3}};
int* v1[] = {values1[0], values1[1], values1[2]};
printf("%d\n", maxSpending(v1, 3, 3));
int values2[][5] = {{10,8,6,4,2},{9,7,5,3,2}};
int* v2[] = {values2[0], values2[1]};
printf("%d\n", maxSpending(v2, 2, 5));
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int MaxSpending(int[][] values) {
List<int> items = new List<int>();
foreach (var shop in values) {
items.AddRange(shop);
}
items.Sort((a, b) => b.CompareTo(a));
int maxSpend = 0, day = 1;
foreach (int value in items) {
maxSpend += value * day++;
}
return maxSpend;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[][] values1 = new int[][] {
new int[] {8, 5, 2},
new int[] {6, 4, 1},
new int[] {9, 7, 3}
};
Console.WriteLine(solution.MaxSpending(values1));
int[][] values2 = new int[][] {
new int[] {10, 8, 6, 4, 2},
new int[] {9, 7, 5, 3, 2}
};
Console.WriteLine(solution.MaxSpending(values2));
}
}From Python, concise integration flourishes by essentially flat packing all immediate items into a simple list. Efficient ordered sorting through Python's internal capabilities lets a simple single-loop addition operation achieve day-aligned multiplication. This further optimizes each attempt for maximizing total spend per available day.
Time Complexity: O(m * n log(m * n)) because of the sorting process.
Space Complexity: O(m * n) as it stores the flattened items in place before sorting.
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.
function maxSpending(values: number[][]): number {
const m = values.length;
const n = values[0].length;
const pq = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });
for (let i = 0; i < m; ++i) {
pq.enqueue([values[i][n - 1], i, n - 1]);
}
let ans = 0;
for (let d = 1; !pq.isEmpty(); ++d) {
const [v, i, j] = pq.dequeue()!;
ans += v * d;
if (j > 0) {
pq.enqueue([values[i][j - 1], i, j - 1]);
}
}
return ans;
}func maxSpending(values [][]int) (ans int64) {
pq := hp{}
n := len(values[0])
for i, row := range values {
heap.Push(&pq, tuple{row[n-1], i, n - 1})
}
for d := 1; len(pq) > 0; d++ {
p := heap.Pop(&pq).(tuple)
ans += int64(p.v * d)
if p.j > 0 {
heap.Push(&pq, tuple{values[p.i][p.j-1], p.i, p.j - 1})
}
}
return
}
type tuple struct{ v, i, j int }
type hp []tuple
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Priority Queue Approach | Time Complexity: |
| Two-Pointer Consolidation Strategy | Time Complexity: |
| Greedy + Priority Queue | – |
Complexity analysis
| 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 |
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.