# Maximum Spending After Buying Items
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-spending-after-buying-items)
Canonical: https://scaleengineer.com/dsa/problems/maximum-spending-after-buying-items
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## 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 _the **maximum amount of money that can be spent** on buying all_ `m * n` _products_.

**Example 1:**

**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:**

**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 <= 104`
* `1 <= values[i][j] <= 106`
* `values[i]` are sorted in non-increasing order.

# Approaches
## Flatten, Sort, and Calculate
This is a straightforward approach based on the greedy strategy. The core idea is that to maximize the total spending, we must pair the smallest item values with the smallest day numbers (1, 2, 3, ...) and the largest item values with the largest day numbers (..., m*n-1, m*n). This is a direct application of the rearrangement inequality. The algorithm first collects all `m * n` item values from the 2D matrix into a single 1D list, then sorts this list in ascending order. Finally, it iterates through the sorted list, multiplying the `i`-th value (1-indexed) with the day number `i` and summing up the results to get the maximum possible spending.
**Time:** O((m*n) * log(m*n)). Flattening takes O(m*n). Sorting `m*n` elements takes O((m*n) * log(m*n)). The final summation takes O(m*n). The dominant part is sorting. · **Space:** O(m*n). We need an auxiliary list to store all `m*n` items.
**Pros:** Simple to understand and implement.; Correctly solves the problem based on the greedy principle.
**Cons:** High space complexity, as it requires storing all `m*n` items in a separate list. This can be memory-intensive for large `m` and `n`.; Time complexity is not optimal, as it involves sorting a large list and doesn't leverage the pre-sorted nature of the rows in the input matrix.
### Explanation
The algorithm begins by creating a one-dimensional list to hold all `m * n` item values. It then iterates through each row and column of the input `values` matrix, adding every item's value to this new list. Once all values are collected, the list is sorted in non-decreasing order. This ensures that the items are ordered from cheapest to most expensive. A variable `totalSpending` is initialized to zero. Another variable `day` is initialized to 1. The algorithm then iterates through the sorted list. For each value `v` at index `i` (0-indexed), it calculates the cost for day `i+1` as `v * (i+1)`. This product is added to `totalSpending`. After iterating through all the values, `totalSpending` holds the maximum possible amount, which is returned. The logic is sound because the buying constraints allow us to pick the globally cheapest available item on any given day. By sorting all values, we are essentially simulating this process: on day 1 we buy the cheapest of all items, on day 2 the second cheapest, and so on.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length;
        int n = values[0].length;
        List<Integer> allItems = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                allItems.add(values[i][j]);
            }
        }

        Collections.sort(allItems);

        long totalSpending = 0;
        long day = 1;
        for (int value : allItems) {
            totalSpending += (long) value * day;
            day++;
        }

        return totalSpending;
    }
}
```
### Algorithm
- Create a new 1D list, say `allItems`, of size `m * n`.
- Iterate through the `values` matrix (from `i=0` to `m-1`, `j=0` to `n-1`).
- Copy each `values[i][j]` into the `allItems` list.
- Sort the `allItems` list in ascending order.
- Initialize `totalSpending = 0` and `day = 1`.
- Iterate through the sorted `allItems` list. For each `value`:
    - `totalSpending += value * day`
    - `day++`
- Return `totalSpending`.

## Iterative Minimum Finding
This approach improves upon the space complexity of the first one by avoiding the creation of a large intermediate list. It simulates the day-by-day buying process directly. On each day, from 1 to `m*n`, we need to buy the cheapest item currently available. The cheapest available item in any shop `i` is the rightmost one that hasn't been bought yet. This approach keeps track of the index of the next item to be bought from each shop. In each step (day), it scans through all `m` shops to find the one with the minimum-valued available item, "buys" it, and updates the index for that shop.
**Time:** O(m^2 * n). The outer loop runs `m*n` times. Inside, we iterate through `m` shops to find the minimum. This results in `(m*n) * m` operations. · **Space:** O(m). We only need an array of size `m` to keep track of the indices for each shop.
**Pros:** Excellent space complexity, much better than the flatten-and-sort approach.; Does not require modifying the input or creating large data structures.; For the given constraints where `m` is small, this can be faster than the flatten-and-sort approach.
**Cons:** The time complexity is quadratic in `m`, which would be inefficient if `m` were large.; Repeatedly scanning all `m` shops to find the minimum is inefficient. A better data structure can optimize this search.
### Explanation
We maintain an array of pointers, say `itemIndices`, of size `m`. `itemIndices[i]` stores the index of the rightmost (cheapest) available item in shop `i`. Initially, all pointers are set to `n-1`. We loop for `m*n` days. In each iteration `d` (from 1 to `m*n`): we search for the overall cheapest item among the currently available items from all shops. We iterate from shop 0 to `m-1`. We keep track of the minimum value found so far (`minVal`) and the shop it belongs to (`shopWithMin`). For each shop `i`, if it still has items left (i.e., `itemIndices[i] >= 0`), we compare `values[i][itemIndices[i]]` with `minVal`. If it's smaller, we update `minVal` and `shopWithMin`. After checking all shops, `minVal` will be the value of the item to buy on day `d`. We add `minVal * d` to our `totalSpending`. We then "buy" this item by decrementing the pointer for the corresponding shop: `itemIndices[shopWithMin]--`. This process is repeated until all items are bought.

```java
import java.util.Arrays;

class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length;
        int n = values[0].length;
        int[] itemIndices = new int[m];
        Arrays.fill(itemIndices, n - 1);

        long totalSpending = 0;
        for (long day = 1; day <= m * n; day++) {
            int minVal = Integer.MAX_VALUE;
            int shopWithMin = -1;

            for (int i = 0; i < m; i++) {
                if (itemIndices[i] >= 0) {
                    if (values[i][itemIndices[i]] < minVal) {
                        minVal = values[i][itemIndices[i]];
                        shopWithMin = i;
                    }
                }
            }

            totalSpending += (long) minVal * day;
            if (shopWithMin != -1) {
                itemIndices[shopWithMin]--;
            }
        }
        return totalSpending;
    }
}
```
### Algorithm
- Initialize an array `itemIndices` of size `m` with all values `n-1`.
- Initialize `totalSpending = 0L`.
- Loop `day` from 1 to `m*n`.
  - Initialize `minVal = infinity` and `shopWithMin = -1`.
  - Iterate `i` from 0 to `m-1`.
    - If shop `i` has items left (`itemIndices[i] >= 0`) and `values[i][itemIndices[i]] < minVal`:
      - Update `minVal = values[i][itemIndices[i]]`.
      - Update `shopWithMin = i`.
  - Add `(long)minVal * day` to `totalSpending`.
  - Decrement `itemIndices[shopWithMin]`.
- Return `totalSpending`.

## Using a Min-Heap to Merge Sorted Lists
This is the most efficient approach. It recognizes the problem as a classic "merge k sorted lists" problem, where `k` is the number of shops `m`. Each shop's items, when read from right to left, form a sorted list (non-decreasing values). We can use a min-heap to efficiently find the minimum element among the `m` available items at any point in time.
**Time:** O((m*n) * log(m)). Initializing the heap takes O(m log m). The loop runs `m*n` times. Each iteration involves one `poll` and at most one `offer`, both taking O(log m) time. Thus, the total time is O(m log m + (m*n) log m) which simplifies to O((m*n) log m). · **Space:** O(m). The heap stores at most one item from each of the `m` shops.
**Pros:** Most efficient approach in terms of both time and space complexity.; Effectively utilizes the sorted property of the input rows.; Scales well even if `m` were larger.
**Cons:** Slightly more complex to implement than the other approaches due to the use of a priority queue.
### Explanation
The algorithm uses a min-heap to keep track of the cheapest available item from each of the `m` shops. The heap stores elements representing an item, for example, as an array `[value, shop_index, item_index]`. The heap is ordered by `value`. Initially, the heap is populated with the cheapest item from each shop, which is the rightmost item `values[i][n-1]` for each shop `i`. So, we add `[values[i][n-1], i, n-1]` for all `i` from 0 to `m-1` into the min-heap. Then, we loop `m*n` times, corresponding to the days. In each iteration `d`: we extract the minimum element from the heap. This element, say `[value, shop_idx, item_idx]`, represents the globally cheapest item available. We calculate the spending for the current day as `value * d` and add it to the `totalSpending`. Since we've "bought" the item from `shop_idx` at `item_idx`, we need to add the next cheapest item from that same shop to the heap. This would be the item at `item_idx - 1`. If `shop_idx` has more items left (i.e., `item_idx - 1 >= 0`), we add the new item `[values[shop_idx][item_idx - 1], shop_idx, item_idx - 1]` to the heap. This process ensures that on each day, we are always picking the absolute cheapest item available among all shops, and we do it efficiently using the heap property.

```java
import java.util.PriorityQueue;

class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length;
        int n = values[0].length;

        // Min-heap to store [value, shop_index, item_index]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // Initialize the heap with the last item from each shop
        for (int i = 0; i < m; i++) {
            minHeap.offer(new int[]{values[i][n - 1], i, n - 1});
        }

        long totalSpending = 0;
        long day = 1;

        while (!minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int value = current[0];
            int shopIdx = current[1];
            int itemIdx = current[2];

            totalSpending += (long) value * day;
            day++;

            // If there are more items in the same shop, add the next one to the heap
            if (itemIdx > 0) {
                int nextItemIdx = itemIdx - 1;
                int nextValue = values[shopIdx][nextItemIdx];
                minHeap.offer(new int[]{nextValue, shopIdx, nextItemIdx});
            }
        }

        return totalSpending;
    }
}
```
### Algorithm
- Create a min-heap that compares elements based on their value.
- For each shop `i` from 0 to `m-1`, add the tuple `(values[i][n-1], i, n-1)` to the heap.
- Initialize `totalSpending = 0L` and `day = 1L`.
- While the heap is not empty:
  - Extract the minimum element `(value, shop_idx, item_idx)` from the heap.
  - Add `(long)value * day` to `totalSpending`.
  - Increment `day`.
  - If `item_idx > 0`, add the next item from the same shop, `(values[shop_idx][item_idx-1], shop_idx, item_idx-1)`, to the heap.
- Return `totalSpending`.

# Solutions
### Java

```java
class Solution {
public
  long maxSpending(int[][] values) {
    int m = values.length, n = values[0].length;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[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; !pq.isEmpty(); ++d) {
      var p = pq.poll();
      int v = p[0], i = p[1], j = p[2];
      ans += (long)v * d;
      if (j > 0) {
        pq.offer(new int[]{values[i][j - 1], i, j - 1});
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxSpending(vector<vector<int>> &values) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                   greater<tuple<int, int, int>>>
        pq;
    int m = values.size(), n = values[0].size();
    for (int i = 0; i < m; ++i) {
      pq.emplace(values[i][n - 1], i, n - 1);
    }
    long long ans = 0;
    for (int d = 1; pq.size(); ++d) {
      auto [v, i, j] = pq.top();
      pq.pop();
      ans += 1LL * v * d;
      if (j) {
        pq.emplace(values[i][j - 1], i, j - 1);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSpending(self, values: List[List[int]]) -> int: n = len(values[0]) pq = [(row[- 1], i, n - 1) for i, row in enumerate(values)] heapify(pq) ans = d = 0 while pq: d += 1 v, i, j = heappop(pq) ans += v * d if j: heappush(pq, (values[i][j - 1], i, j - 1)) return ans

```