Maximum spending after buying items

Array Greedy Sorting Heap (Priority Queue) Matrix

61.3% acceptance

Feb 25, 2026

118

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]. The items in the ith shop are sorted in non-increasing order. On each day, you buy the rightmost available item from a chosen shop for price values[i][j] * d. Return the maximum amount of money that can be spent on buying all m * n products.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_spending(values: Vec<Vec<i32>>) -> i64 {
    // Sort all items globally in non-decreasing order, pair with days 1, 2, ..., m*n
    let mut all: Vec<i32> = values.into_iter().flatten().collect();
    all.sort_unstable();
    all.iter().enumerate().map(|(i, &v)| (i as i64 + 1) * v as i64).sum()
  }
}