Maximum Spending After Buying Items — Problem & Solution
Maximum Spending After Buying Items solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Spending After Buying Items is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Zomato interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google, Zomato
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are m shops, each selling n items. values[i][j] is the value of item j in shop i, and each shop's items are sorted in non-increasing order (values[i][j] >= values[i][j + 1]).
On day d (starting from day 1) you buy exactly one item: you choose a shop and buy its rightmost remaining item, paying values[i][j] * d. After m * n days every item has been bought.
Return the maximum total amount you can spend.
Constraint note: the sizes and values are capped (n <= 100, values[i][j] <= 1000; the original allows 10^4 and 10^6) so the total fits in a 32-bit integer.
Example 1
Input: values = [[5,3],[4,1]]
Output: 39
Explanation: Buy 1, 3, 4, 5 on days 1 to 4: 1 + 6 + 12 + 20 = 39.
Example 2
Input: values = [[10,8,6,4,2],[9,7,5,3,2]]
Output: 386
Example 3
Input: values = [[7]]
Output: 7
Constraints
1 <= m == values.length <= 101 <= n == values[i].length <= 1001 <= values[i][j] <= 1000values[i][j] >= values[i][j + 1]
Hints for Maximum Spending After Buying Items
Hint 1
Day multipliers grow, so expensive items should be bought as late as possible.
Hint 2
Because every row is non-increasing, a shop's rightmost item is its cheapest — the globally cheapest remaining item is always available.
Hint 3
Buy the cheapest available item each day (a min-heap over the shops' rightmost items), which is the same as multiplying the sorted list of all values by 1, 2, 3, ...
How to solve Maximum Spending After Buying Items
By the rearrangement inequality, pairing the smallest values with the smallest day numbers maximises sum(value * day). The shop rule never gets in the way: the cheapest remaining item overall is always some shop's rightmost item.
Approach
- Collect every value (or keep a min-heap of each shop's rightmost item).
- Take values in ascending order; the
d-th one is bought on dayd. - Add
value * dfor each and return the total.
Why it works
Swapping any two purchases that are out of order (a pricier item bought before a cheaper one) increases the total by (big - small) * (later - earlier) >= 0, so ascending order is optimal among all orders. And it is achievable: each row is sorted non-increasing, so its rightmost remaining item is its minimum, hence the global minimum is always on offer.
Complexity
- Time —
O(mn log(mn)) - Space —
O(mn)
Pitfalls
- Buying the largest item first is the intuitive but wrong direction — the multiplier rewards waiting.
- Day numbers start at 1, not 0.
- With the original limits the total needs 64 bits.
Reference solution
Python
from typing import List
def maxSpending(values: List[List[int]]) -> int:
items = sorted(v for row in values for v in row)
return sum(v * (d + 1) for d, v in enumerate(items))Java
public static int maxSpending(int[][] values) {
int m = values.length, n = values[0].length;
int[] items = new int[m * n];
int at = 0;
for (int[] row : values) for (int v : row) items[at++] = v;
Arrays.sort(items);
long total = 0;
for (int d = 0; d < items.length; d++) total += (long) items[d] * (d + 1);
return (int) total;
}C++
int maxSpending(vector<vector<int>>& values) {
vector<int> items;
for (auto& row : values) for (int v : row) items.push_back(v);
sort(items.begin(), items.end());
long long total = 0;
for (size_t d = 0; d < items.size(); d++) total += (long long) items[d] * (long long) (d + 1);
return (int) total;
}JavaScript
var maxSpending = function(values) {
var items = [];
for (var i = 0; i < values.length; i++) {
for (var j = 0; j < values[i].length; j++) items.push(values[i][j]);
}
items.sort(function(a, b) { return a - b; });
var total = 0;
for (var d = 0; d < items.length; d++) total += items[d] * (d + 1);
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms