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 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 _themaximum amount of money that can be spent on buying all _ m * n products.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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 <= 10^4
  • 1 <= values[i][j] <= 10^6
  • values[i] are sorted in non-increasing order.

Solution

Method 1 – Greedy with Min-Heap (Priority Queue)

Intuition

To maximize the total spending, we want to buy the cheapest available item on the earliest day (when the multiplier is smallest), and the most expensive items on the latest days (when the multiplier is largest). This is achieved by always picking the rightmost (smallest) item from any shop each day, using a min-heap to efficiently select the minimum.

Approach

  1. For each shop, start with the rightmost item (smallest value, largest index).
  2. Use a min-heap to keep track of the current rightmost item from each shop, storing (value, shop index, item index).
  3. For each day from 1 to m*n:
    • Pop the smallest value from the heap.
    • Add value * day to the total spending.
    • If there are more items left in that shop, push the next rightmost item from that shop into the heap.
  4. Continue until all items are bought.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        int m = values.size(), n = values[0].size();
        using T = tuple<int, int, int>;
        priority_queue<T, vector<T>, greater<T>> pq;
        for (int i = 0; i < m; ++i)
            pq.emplace(values[i][n-1], i, n-1);
        long long ans = 0;
        for (int d = 1; d <= m * n; ++d) {
            auto [v, i, j] = pq.top(); pq.pop();
            ans += 1LL * v * d;
            if (j > 0) pq.emplace(values[i][j-1], i, j-1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import "container/heap"
type Item struct{v, i, j int}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].v < h[j].v }
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; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func maxSpending(values [][]int) int64 {
    m, n := len(values), len(values[0])
    h := &MinHeap{}
    for i := 0; i < m; i++ {
        heap.Push(h, Item{values[i][n-1], i, n-1})
    }
    var ans int64
    for d := 1; d <= m*n; d++ {
        x := heap.Pop(h).(Item)
        ans += int64(x.v) * int64(d)
        if x.j > 0 {
            heap.Push(h, Item{values[x.i][x.j-1], x.i, x.j-1})
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length, n = values[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < m; ++i)
            pq.offer(new int[]{values[i][n-1], i, n-1});
        long ans = 0;
        for (int d = 1; d <= m * n; ++d) {
            int[] x = pq.poll();
            ans += 1L * x[0] * d;
            if (x[2] > 0) pq.offer(new int[]{values[x[1]][x[2]-1], x[1], x[2]-1});
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.PriorityQueue
class Solution {
    fun maxSpending(values: Array<IntArray>): Long {
        val m = values.size; val n = values[0].size
        val pq = PriorityQueue(compareBy<Triple<Int, Int, Int>> { it.first })
        for (i in 0 until m) pq.add(Triple(values[i][n-1], i, n-1))
        var ans = 0L
        for (d in 1..(m*n)) {
            val (v, i, j) = pq.poll()
            ans += v.toLong() * d
            if (j > 0) pq.add(Triple(values[i][j-1], i, j-1))
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import heapq
class Solution:
    def maxSpending(self, values: list[list[int]]) -> int:
        m, n = len(values), len(values[0])
        pq = [(values[i][n-1], i, n-1) for i in range(m)]
        heapq.heapify(pq)
        ans = 0
        for d in range(1, m*n+1):
            v, i, j = heapq.heappop(pq)
            ans += v * d
            if j > 0:
                heapq.heappush(pq, (values[i][j-1], i, j-1))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn max_spending(values: Vec<Vec<i32>>) -> i64 {
        let m = values.len();
        let n = values[0].len();
        let mut heap = BinaryHeap::new();
        for i in 0..m {
            heap.push(Reverse((values[i][n-1], i, n-1)));
        }
        let mut ans = 0i64;
        for d in 1..=m*n {
            let Reverse((v, i, j)) = heap.pop().unwrap();
            ans += v as i64 * d as i64;
            if j > 0 {
                heap.push(Reverse((values[i][j-1], i, j-1)));
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maxSpending(values: number[][]): number {
        const m = values.length, n = values[0].length;
        const pq: [number, number, number][] = [];
        for (let i = 0; i < m; ++i) pq.push([values[i][n-1], i, n-1]);
        pq.sort((a, b) => a[0] - b[0]);
        let ans = 0;
        for (let d = 1; d <= m * n; ++d) {
            pq.sort((a, b) => a[0] - b[0]);
            const [v, i, j] = pq.shift()!;
            ans += v * d;
            if (j > 0) pq.push([values[i][j-1], i, j-1]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn log m), where m is the number of shops and n is the number of items per shop. Each heap operation is O(log m) and there are mn operations.
  • 🧺 Space complexity: O(m), for the heap storing one item per shop.