Maximum Grid Selection Sum Under Row Limits
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given an `n` by `m` integer matrix `grid`, an array `limits` of length `n`, and an integer `k`.
Select at most `k` matrix elements in total. From row `i`, select no more than `limits[i]` elements. Return the largest possible sum of the selected values.
Different cells are separate choices even when their values are equal. You may select no elements, whose sum is zero.
```cpp
class Solution {
public:
long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k);
};
```
### Examples
**Example 1:**
```text
Input: grid = [[9,8,1],[7,6,5]], limits = [1,2], k = 3
Output: 22
Explanation: Select 9 from row 0 and 7 and 6 from row 1. Their sum is 22. Selecting both 9 and 8 would violate row 0's limit.
```
**Example 2:**
```text
Input: grid = [[100,90],[4,0]], limits = [0,2], k = 2
Output: 4
Explanation: No element may be taken from row 0. Taking the value 4 from row 1 gives the maximum sum; also selecting its zero would not change that sum.
```
### Constraints
- `n == grid.length == limits.length`.
- `m == grid[i].length`.
- `1 <= n, m <= 500`.
- `0 <= grid[i][j] <= 100000`.
- `0 <= limits[i] <= m`.
- `0 <= k <= min(n * m, sum(limits))`.
### Clarifying Questions
- Must exactly `k` elements be selected? No. `k` is an upper bound.
- Is there a restriction on selected columns? No; only the total count and each row's limit matter.
- Can a row contribute zero elements? Yes, including when its limit is positive.
- Must the selected cells be returned? No, return only the maximum sum.
### What a Strong Answer Covers
- Enforces each row's count limit and the overall selection bound together.
- Explains why the chosen values give a maximum sum.
- Handles zero limits, `k = 0`, repeated values, and zero-valued elements.
- Gives time and memory bounds for the full matrix size and uses a sufficiently wide sum type.
### Follow-up Questions
- Why does the nonnegative-value constraint matter when reasoning about selecting fewer than `k` elements?
- Can equal values in different cells both contribute to a valid selection?
```hint Eliminate values that cannot be necessary
Within a row, a selected smaller value can be exchanged for an unselected larger value without changing either count constraint. Consider which values must remain available after applying that observation.
```
Overview: Maximize the sum of at most k matrix elements while respecting each row's selection limit. Includes zero-limit examples and a complete C++ solution with proof.
