LeetCode Problem 2931

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting, Heap (Priority Queue), Matrix

Solution

LeetCode 2931 - Maximum Spending After Buying Items

Problem Understanding

We are given an m × n matrix values where each row represents a shop and each column represents an item in that shop.

The important property is that every row is sorted in non-increasing order:

values[i][0] >= values[i][1] >= ... >= values[i][n-1]

When buying from a shop, we are not allowed to choose any arbitrary item. We must always buy the rightmost remaining item in that shop.

If a shop currently has:

[8, 5, 2]

then we must buy 2 first, then 5, then 8.

On day d, the price paid for an item with value v is:

v × d

We buy exactly one item per day until all m × n items are purchased.

The goal is to maximize the total amount spent.

The constraints are:

• m ≤ 10
• n ≤ 10^4
• Total number of items can reach 10^5
• Item values can be as large as 10^6

Since there may be up to one hundred thousand items, any solution that repeatedly scans all remaining items to decide the next purchase will be too slow.

A crucial observation is that every row behaves like a sorted sequence that becomes available from right to left.

Important edge cases include:

• A single shop.
• A single item.
• Rows containing equal values.
• Very large values requiring 64-bit arithmetic.
• Maximum-sized inputs with 100,000 total items.

The problem guarantees that each row is already sorted in non-increasing order, which is the key property that enables an efficient solution.

Approaches

Brute Force

A direct approach is to simulate the buying process day by day.

At every day, we determine every currently available item, meaning the rightmost remaining item of each shop. Among those candidates, we choose the item that leads to the optimal future result.

To maximize spending, we would like smaller values to receive smaller day multipliers and larger values to receive larger day multipliers. Therefore, at each step we would choose the smallest currently available item.

The issue is efficiency. If we scan all shops every day to find the smallest available item, we perform:

(m × n) days

and each day requires:

O(m)

work.

Since there can be 100,000 purchases, this becomes unnecessarily expensive.

Key Insight

Suppose we have two values:

a ≤ b

and two day numbers:

x < y

Consider the two possible assignments:

a*x + b*y

versus

a*y + b*x

The difference is:

(a*x + b*y) - (a*y + b*x)
= (b-a)(y-x)
≥ 0

Therefore, assigning the larger value to the larger day never decreases the answer.

This is a classic exchange argument.

To maximize total spending:

• Smaller values should be bought earlier.
• Larger values should be bought later.

The available items from all shops form multiple sorted streams. The currently available item of each shop is always the smallest remaining item in that shop because we buy from right to left.

Therefore, the problem becomes:

Repeatedly extract the globally smallest currently available item.

A min-heap is perfect for this task.

Each shop contributes one candidate item to the heap. Whenever an item is purchased, the next item from that same shop becomes available and is inserted into the heap.

This is essentially a k-way merge of sorted sequences.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m²n)	O(m)	Scan all shops every day to find the smallest available item
Optimal	O(mn log m)	O(m)	Min-heap maintains the globally smallest available item

Algorithm Walkthrough

1. Let m be the number of shops and n be the number of items per shop.
2. For every shop, insert its rightmost item into a min-heap. The heap entry stores:

• item value
• row index
• column index

Since the rightmost item is the only purchasable item from that shop initially, these are the first candidates. 3. Initialize:

• day = 1
• answer = 0

4. While the heap is not empty:

• Extract the smallest value from the heap.
• Add value × day to the answer.
• Increment day.

5. Suppose the extracted item came from position (row, col).

After purchasing it, the next available item in that shop becomes (row, col - 1). 6. If col > 0, push:

• values[row][col - 1]
• row
• col - 1

into the heap. 7. Continue until every item has been purchased. 8. Return the accumulated answer.

Why it works

At every step, the heap chooses the smallest value among all currently available items. By the exchange argument, smaller values should receive smaller day multipliers and larger values should receive larger day multipliers. The heap guarantees exactly this ordering while respecting the constraint that items in each shop must be bought from right to left. Since every purchase reveals at most one new item from the same shop, the heap always contains precisely the set of legal next choices. Therefore the resulting schedule is optimal.

Python Solution

from typing import List
import heapq

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        m = len(values)
        n = len(values[0])

        heap = []

        for row in range(m):
            heapq.heappush(heap, (values[row][n - 1], row, n - 1))

        day = 1
        answer = 0

        while heap:
            value, row, col = heapq.heappop(heap)

            answer += value * day
            day += 1

            if col > 0:
                heapq.heappush(
                    heap,
                    (values[row][col - 1], row, col - 1)
                )

        return answer

The implementation begins by inserting the rightmost item from every shop into a min-heap. These are exactly the items that can legally be purchased first.

The heap always stores the current purchasable item from each shop. Removing the minimum element gives the smallest available value across all shops.

After buying an item, we add its contribution value * day to the answer. The next item to the left in the same row becomes available and is inserted into the heap.

Because each item enters the heap exactly once and leaves exactly once, the algorithm efficiently processes all purchases while maintaining the optimal ordering.

Go Solution

package main

import "container/heap"

type Item struct {
	value int
	row   int
	col   int
}

type MinHeap []Item

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].value < h[j].value
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func maxSpending(values [][]int) int64 {
	m := len(values)
	n := len(values[0])

	h := &MinHeap{}
	heap.Init(h)

	for r := 0; r < m; r++ {
		heap.Push(h, Item{
			value: values[r][n-1],
			row:   r,
			col:   n - 1,
		})
	}

	var answer int64 = 0
	var day int64 = 1

	for h.Len() > 0 {
		item := heap.Pop(h).(Item)

		answer += int64(item.value) * day
		day++

		if item.col > 0 {
			heap.Push(h, Item{
				value: values[item.row][item.col-1],
				row:   item.row,
				col:   item.col - 1,
			})
		}
	}

	return answer
}

The Go solution follows the same algorithm but uses the container/heap package. Since the result can exceed 32-bit integer limits, the accumulated answer and day counter are stored as int64. The custom heap stores the value along with its row and column coordinates so that the next available item from the same shop can be located efficiently.

Worked Examples

Example 1

values =
[
  [8,5,2],
  [6,4,1],
  [9,7,3]
]

Initial heap:

Value	Shop	Column
1	1	2
2	0	2
3	2	2

Day	Popped Value	Contribution	Running Total
1	1	1×1=1	1
2	2	2×2=4	5
3	3	3×3=9	14
4	4	4×4=16	30
5	5	5×5=25	55
6	6	6×6=36	91
7	7	7×7=49	140
8	8	8×8=64	204
9	9	9×9=81	285

Final answer:

285

Example 2

values =
[
  [10,8,6,4,2],
  [9,7,5,3,2]
]

Initial heap:

Value	Shop
2	0
2	1

Purchases occur in ascending order:

2, 2, 3, 4, 5, 6, 7, 8, 9, 10

Day	Value	Contribution
1	2	2
2	2	4
3	3	9
4	4	16
5	5	25
6	6	36
7	7	49
8	8	64
9	9	81
10	10	100

Total:

386

Complexity Analysis

Measure	Complexity	Explanation
Time	O(mn log m)	Each item is inserted and removed once, heap size never exceeds m
Space	O(m)	Heap contains at most one active item per shop

The heap never stores more than one currently available item from each shop, so its size is bounded by m ≤ 10. Every one of the m × n items performs one insertion and one removal, and each heap operation costs O(log m). Therefore the total complexity is O(mn log m).

Test Cases

from typing import List

s = Solution()

assert s.maxSpending([[8,5,2],[6,4,1],[9,7,3]]) == 285  # example 1

assert s.maxSpending([[10,8,6,4,2],[9,7,5,3,2]]) == 386  # example 2

assert s.maxSpending([[5]]) == 5  # single item

assert s.maxSpending([[5,4,3,2,1]]) == 55  # single shop

assert s.maxSpending([[5],[4],[3]]) == 26  # single column

assert s.maxSpending([[1,1,1],[1,1,1]]) == 21  # all equal values

assert s.maxSpending([[1000000]]) == 1000000  # maximum value

assert s.maxSpending([[4,3],[2,1]]) == 30  # small matrix

assert s.maxSpending([[9,8,1],[7,6,2]]) == 122  # interleaving rows

assert s.maxSpending([[10,9,8],[7,6,5],[4,3,2]]) == 330  # larger ordering test

Test Summary

Test	Why
[[8,5,2],[6,4,1],[9,7,3]]	Official example 1
[[10,8,6,4,2],[9,7,5,3,2]]	Official example 2
[[5]]	Smallest possible input
[[5,4,3,2,1]]	Single row
[[5],[4],[3]]	Single column
Equal values matrix	Handles duplicates correctly
[[1000000]]	Maximum value size
[[4,3],[2,1]]	Small sanity check
[[9,8,1],[7,6,2]]	Heap interleaving between rows
Three-row example	General correctness

Edge Cases

Single Item

When m = 1 and n = 1, there is exactly one purchase. The heap contains one element, which is popped on day 1. The answer is simply that value. The implementation naturally handles this without any special logic.

Single Shop

With only one shop, every item must be bought from right to left. The heap never contains more than one element. The algorithm degenerates into repeatedly exposing the next item in the row, which still produces the optimal ordering because there is no freedom of choice.

Equal Values

Multiple shops may expose identical values at the same time. The heap may return them in any order. Since equal values contribute the same regardless of which equal-valued item receives which day multiplier, every tie ordering produces the same total. Therefore correctness does not depend on tie-breaking.

Very Large Answers

There can be up to 100,000 items, values can reach 10^6, and day numbers can also reach 100,000. The final result can be on the order of 10^16, which exceeds 32-bit integer limits. The Python solution uses arbitrary-precision integers automatically, while the Go solution explicitly uses int64 to avoid overflow.

Maximum Input Size

The largest test contains 10 × 10,000 = 100,000 items. A naive approach that repeatedly scans all possibilities would perform unnecessary work. The heap-based solution processes each item exactly once and keeps only m active candidates, allowing it to comfortably handle the maximum constraints.