Maximum Spending After Buying Items

Hard
1434.

Maximum Spending After Buying Items

HardArrayGreedySortingHeap (Priority Queue)AmazonGoogleZomato

Maximum Spending After Buying Items is a hard coding problem on arrays, sorting and greedy, asked in Amazon, Google and Zomato interviews.

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 <= 10
  • 1 <= n == values[i].length <= 100
  • 1 <= values[i][j] <= 1000
  • values[i][j] >= values[i][j + 1]
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} values
 * @return {number}
 */
var maxSpending = function(values) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 10
  • 1 <= n == values[i].length <= 100
  • 1 <= values[i][j] <= 1000
  • values[i][j] >= values[i][j + 1]

Hints for Maximum Spending After Buying Items

  1. Hint 1

    Day multipliers grow, so expensive items should be bought as late as possible.

  2. Hint 2

    Because every row is non-increasing, a shop's rightmost item is its cheapest — the globally cheapest remaining item is always available.

  3. 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

  1. Collect every value (or keep a min-heap of each shop's rightmost item).
  2. Take values in ascending order; the d-th one is bought on day d.
  3. Add value * d for 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