Skip to content

2931. Maximum Spending After Buying Items

  • Time: $O(mn\log mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  long long maxSpending(vector<vector<int>>& values) {
    const int m = values.size();
    const int n = values[0].size();
    long ans = 0;
    long d = 1;
    vector<int> items;

    for (const vector<int>& shop : values)
      for (const int item : shop)
        items.push_back(item);

    ranges::sort(items);

    for (const int item : items)
      ans += item * d++;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public long maxSpending(int[][] values) {
    int[] sorted = Arrays.stream(values)
                       .flatMapToInt(Arrays::stream) //
                       .sorted()                     //
                       .toArray();                   //
    return LongStream.range(0, sorted.length)
        .map(i -> (i + 1) * sorted[(int) i]) //
        .sum();                              //
  }
}

1
2
3
4
class Solution:
  def maxSpending(self, values: list[list[int]]) -> int:
    items = sorted(item for shop in values for item in shop)
    return sum(item * d for d, item in enumerate(items, 1))