# Maximum Sum With at Most K Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-with-at-most-k-elements)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-with-at-most-k-elements
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## Problem
You are given a 2D integer matrix `grid` of size `n x m`, an integer array `limits` of length `n`, and an integer `k`. The task is to find the **maximum sum** of **at most** `k` elements from the matrix `grid` such that:

* The number of elements taken from the `ith` row of `grid` does not exceed `limits[i]`.

Return the **maximum sum**.

**Example 1:**

**Input:** grid = \[\[1,2\],\[3,4\]\], limits = \[1,2\], k = 2

**Output:** 7

**Explanation:**

* From the second row, we can take at most 2 elements. The elements taken are 4 and 3.
* The maximum possible sum of at most 2 selected elements is `4 + 3 = 7`.

**Example 2:**

**Input:** grid = \[\[5,3,7\],\[8,2,6\]\], limits = \[2,2\], k = 3

**Output:** 21

**Explanation:**

* From the first row, we can take at most 2 elements. The element taken is 7.
* From the second row, we can take at most 2 elements. The elements taken are 8 and 6.
* The maximum possible sum of at most 3 selected elements is `7 + 8 + 6 = 21`.

**Constraints:**

* `n == grid.length == limits.length`
* `m == grid[i].length`
* `1 <= n, m <= 500`
* `0 <= grid[i][j] <= 105`
* `0 <= limits[i] <= m`
* `0 <= k <= min(n * m, sum(limits))`

# Approaches
## Dynamic Programming (Knapsack-style)
This problem can be modeled as a variation of the Multiple-Choice Knapsack problem. For each row (item type), we can choose to take `c` elements (items), where `c` is between 0 and `limits[i]`. The 'weight' of taking `c` elements is `c`, and the 'value' is the sum of the `c` largest elements in that row. The total 'weight' (number of elements) cannot exceed `k`. We want to maximize the total 'value' (sum).

A standard dynamic programming approach can solve this. We define `dp[j]` as the maximum sum we can obtain by choosing a total of `j` elements from the rows considered so far. We iterate through each row and update the `dp` array based on the choices available for that row.
**Time:** O(n*m*log(m) + n*k*m). `O(n*m*log(m))` for sorting all rows. The DP calculation involves three nested loops, iterating up to `n`, `k`, and `m` times respectively, leading to `O(n*k*m)`. · **Space:** O(n*m + k). `O(n*m)` for storing the prefix sums and `O(k)` for the DP array.
**Pros:** It's a standard and relatively intuitive approach for knapsack-like problems.; The logic is guaranteed to find the optimal solution.
**Cons:** The time complexity of `O(n * k * m)` is too high for the given constraints, especially when `k` and `m` are large. This will likely result in a 'Time Limit Exceeded' error.
### Explanation
First, we preprocess the data to make the DP transitions efficient. For each row, we sort it in descending order to easily access the largest elements. Then, we compute the prefix sums for each sorted row. `prefixSums[i][c]` will store the sum of the `c` largest elements of row `i`.

The DP state `dp[j]` represents the maximum sum using exactly `j` elements. We use a 1D array for space optimization. We iterate through each row `i` and for each row, we update the `dp` array. We iterate the total elements `j` from `k` down to `1` (to avoid using elements from the same row multiple times in a single update step). For each `j`, we consider taking `c` elements from the current row `i`, where `c` ranges from 1 to `limits[i]`. The new `dp[j]` will be the maximum of its current value and `dp[j-c] + prefixSums[i][c]`, which represents the sum from previous rows plus the sum from taking `c` elements from the current row.

After iterating through all the rows, the `dp` array holds the maximum sums for taking exactly `0, 1, ..., k` elements. The final answer is the maximum value in this `dp` array.

```java
class Solution {
    public long maximumSum(int[][] grid, int[] limits, int k) {
        int n = grid.length;
        int m = grid[0].length;

        // 1. Preprocessing: Sort rows and compute prefix sums
        long[][] prefixSums = new long[n][m + 1];
        for (int i = 0; i < n; i++) {
            Arrays.sort(grid[i]);
            // Reverse for descending order
            for (int l = 0, r = m - 1; l < r; l++, r--) {
                int temp = grid[i][l];
                grid[i][l] = grid[i][r];
                grid[i][r] = temp;
            }
            
            prefixSums[i][0] = 0;
            for (int j = 0; j < m; j++) {
                prefixSums[i][j + 1] = prefixSums[i][j] + grid[i][j];
            }
        }

        // 2. DP with space optimization
        long[] dp = new long[k + 1];

        for (int i = 0; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                for (int c = 1; c <= Math.min(j, limits[i]); c++) {
                    if (j - c >= 0) {
                        dp[j] = Math.max(dp[j], dp[j - c] + prefixSums[i][c]);
                    }
                }
            }
        }

        // 3. Result is the max value in the dp array
        long maxSum = 0;
        for (long sum : dp) {
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }
}
```
### Algorithm
1. **Preprocessing**:
   - For each row `i` in the `grid`, sort it in descending order.
   - For each row `i`, compute its prefix sums. Let `P[i][j]` be the sum of the `j` largest elements in row `i`. `P[i][0]` is 0.
2. **Dynamic Programming Setup**:
   - Create a 1D DP array, `dp`, of size `k + 1`, initialized to zeros. `dp[j]` will store the maximum sum achievable using exactly `j` elements from the rows processed so far.
3. **DP Iteration**:
   - Iterate through each row `i` from `0` to `n-1`.
   - For each row, update the `dp` array. Iterate `j` from `k` down to `1`.
   - For each `j`, iterate through the number of elements `c` to take from the current row `i`, where `1 <= c <= limits[i]` and `c <= j`.
   - The transition is: `dp[j] = max(dp[j], dp[j - c] + P[i][c])`.
4. **Result**:
   - Since we can take *at most* `k` elements and all element values are non-negative, the maximum sum will be the largest value in the `dp` array after processing all rows. The answer is `max(dp[0], dp[1], ..., dp[k])`.

## Greedy Approach with Max-Heap
A more efficient method is a greedy approach. Since we want to maximize the sum, it's always optimal to pick the largest available element at each step. We can maintain the 'largest available element' from each row and pick the best among them.

This can be implemented efficiently using a max-heap. The heap will store the next-best candidate element from each row. At each step, we extract the overall best element from the heap, add it to our sum, and then insert the next-best element from the same row back into the heap, provided we don't violate that row's specific limit.
**Time:** O(n*m*log(m) + k*log(n)). `O(n*m*log(m))` for sorting all rows. The main loop runs up to `k` times, with each heap operation (pop and push) taking `O(log(n))` time. · **Space:** O(n*m). `O(n*m)` to store the grid (if modification is not allowed, otherwise can be `O(1)` for sorting in-place). The heap requires `O(n)` space.
**Pros:** Significantly more efficient than the DP approach.; Guaranteed to be optimal.; The logic is intuitive and reflects the nature of the problem (maximizing a sum).
**Cons:** The time complexity is dependent on `k`. If `k` is very large (close to `n*m`), this approach can be slower than the binary search method.
### Explanation
The core idea is that to get the maximum sum, we should always pick the largest available number. The constraints are that we can pick at most `k` numbers in total, and from each row `i`, at most `limits[i]` numbers.

First, we sort each row in descending order. This makes it easy to find the 1st, 2nd, 3rd, etc., largest elements of any row.

We use a max-heap to keep track of the current best candidate from each row. Initially, we populate the heap with the largest element of each row. Then, we repeat `k` times: extract the max element from the heap. Suppose this element came from row `r`. We add its value to our total sum. Then, we offer the next largest element from row `r` to the heap, but only if we haven't exhausted the elements in row `r` or exceeded the `limits[r]` for that row. This process ensures that at every step, we are picking the globally largest element available that satisfies all constraints.

This greedy strategy is optimal because of an exchange argument: if there were a better solution, it must differ from the greedy one at some step. At the first differing step, the greedy algorithm chose an element `g` while the optimal solution chose `o`. By the greedy choice property, `g >= o`. We can swap `o` with `g` in the optimal solution to get an equally good or better solution, moving it closer to the greedy solution. Repeating this proves the greedy solution is optimal.

```java
class Solution {
    public long maximumSum(int[][] grid, int[] limits, int k) {
        int n = grid.length;
        int m = grid[0].length;

        // 1. Sort each row in descending order
        for (int i = 0; i < n; i++) {
            Arrays.sort(grid[i]);
            for (int l = 0, r = m - 1; l < r; l++, r--) {
                int temp = grid[i][l];
                grid[i][l] = grid[i][r];
                grid[i][r] = temp;
            }
        }

        // Max-heap to store {value, row_index}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        
        // 2. Initialize heap with the largest element from each row
        for (int i = 0; i < n; i++) {
            if (limits[i] > 0 && m > 0) {
                pq.offer(new int[]{grid[i][0], i});
            }
        }

        long totalSum = 0;
        int[] rowIndices = new int[n]; // Tracks elements taken from each row

        // 3. Greedily pick up to k largest elements
        for (int i = 0; i < k && !pq.isEmpty(); i++) {
            int[] top = pq.poll();
            int value = top[0];
            int row = top[1];

            totalSum += value;
            rowIndices[row]++;
            
            // If there are more elements in the row and we haven't hit the limit,
            // offer the next element from that row to the heap.
            if (rowIndices[row] < m && rowIndices[row] < limits[row]) {
                pq.offer(new int[]{grid[row][rowIndices[row]], row});
            }
        }

        return totalSum;
    }
}
```
### Algorithm
1. **Preprocessing**:
   - Sort each row of the `grid` in descending order. This allows us to access the largest elements of each row sequentially.
2. **Setup Max-Heap**:
   - Create a max-heap (Priority Queue) to store entries of `{value, rowIndex}`.
   - Initialize the heap by adding the largest element from each row `i` (i.e., `grid[i][0]`), provided `limits[i] > 0` and the row is not empty.
3. **Greedy Selection**:
   - Initialize `totalSum = 0` and an array `rowIndices` to track the index of the next element to consider from each row.
   - Loop up to `k` times or until the heap is empty:
     - Extract the element with the maximum value from the heap. Let this be `{value, row}`.
     - Add `value` to `totalSum`.
     - Increment the index for the `row` (`rowIndices[row]++`).
     - If there are more elements to consider in that `row` (i.e., `rowIndices[row] < m`) and the row's limit has not been reached (`rowIndices[row] < limits[row]`), add the next largest element from that row (`grid[row][rowIndices[row]]`) to the heap.
4. **Result**:
   - Return `totalSum`.

## Binary Search on Element Value
The most efficient approach uses binary search on the answer. Instead of picking elements one by one, we can determine a threshold value `T` and decide to pick all elements greater than or equal to `T`. The number of elements we can pick is a monotonic function of `T`: the lower the threshold `T`, the more elements we can pick.

This monotonicity allows us to binary search for the optimal threshold `T`, which represents the value of the smallest element in our chosen set of `k` elements. After finding this threshold, we can calculate the total sum by summing up all elements greater than `T` and then adding `T` for the remaining slots up to `k`.
**Time:** O(n*m*log(m) + n*log(m)*log(V)). The dominant part is sorting, `O(n*m*log(m))`. The binary search runs `log(V)` times (where `V` is the max value of an element), and each check takes `O(n*log(m))`. The final calculation also takes `O(n*log(m))`. This is effectively dominated by the initial sort. · **Space:** O(n*m). `O(n*m)` is needed for storing the sorted grid and the prefix sums.
**Pros:** This is the most efficient approach, with a time complexity that does not depend on `k`.; It performs very well, especially for large values of `k`.
**Cons:** The logic is more complex to understand and implement correctly compared to the greedy approach.; Requires careful handling of edge cases in the binary search and final sum calculation.
### Explanation
This approach hinges on binary searching for the value of the `k`-th largest element we select. Let's call this threshold `T`.

First, we preprocess by sorting each row in descending order and calculating their prefix sums. This allows for efficient queries later.

We then perform a binary search on the possible values of elements, from 0 to 100001. For a given value `mid` in our search, we define a function `check(mid)` that determines if it's possible to select at least `k` elements from the grid with values `>= mid`, while respecting the `limits` for each row. `check(mid)` works by iterating through each row, finding how many elements are `>= mid` (using binary search on the sorted row), taking the minimum of that count and `limits[i]`, and summing these counts up. If the total count is `>= k`, `check(mid)` returns true.

The main binary search aims to find the largest value `T` for which `check(T)` is true. This `T` is the minimum value an element can have to be included in our top `k` choices.

To calculate the final sum, we first take all elements strictly greater than `T`. For each row, we find how many elements are `> T`, take the minimum of this count and `limits[i]`, and use our prefix sum array to add their sum to our `totalSum`. We also count how many elements we've taken so far (`elementsCount`). Finally, we need to take `k - elementsCount` more elements. By the definition of our threshold `T`, all these must have the value `T`. So, we add `(k - elementsCount) * T` to our `totalSum`.

```java
class Solution {
    public long maximumSum(int[][] grid, int[] limits, int k) {
        int n = grid.length;
        int m = grid[0].length;

        // 1. Preprocessing
        for (int i = 0; i < n; i++) {
            Arrays.sort(grid[i]);
            for (int l = 0, r = m - 1; l < r; l++, r--) {
                int temp = grid[i][l];
                grid[i][l] = grid[i][r];
                grid[i][r] = temp;
            }
        }
        long[][] prefixSums = new long[n][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                prefixSums[i][j + 1] = prefixSums[i][j] + grid[i][j];
            }
        }

        // 2. Binary search for the threshold value T
        int low = 0, high = 100001, T = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canTakeAtLeastK(grid, limits, k, mid)) {
                T = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // 3. Calculate final sum
        long totalSum = 0;
        int elementsCount = 0;
        for (int i = 0; i < n; i++) {
            int countGreaterThanT = countGreater(grid[i], T);
            int numToTake = Math.min(countGreaterThanT, limits[i]);
            totalSum += prefixSums[i][numToTake];
            elementsCount += numToTake;
        }

        if (elementsCount < k) {
            totalSum += (long)(k - elementsCount) * T;
        }

        return totalSum;
    }

    private boolean canTakeAtLeastK(int[][] grid, int[] limits, int k, int threshold) {
        long count = 0;
        for (int i = 0; i < grid.length; i++) {
            count += Math.min(countGreaterOrEqual(grid[i], threshold), limits[i]);
            if (count >= k) return true;
        }
        return false;
    }

    private int countGreaterOrEqual(int[] row, int val) {
        int l = 0, r = row.length - 1, ans = row.length;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (row[mid] < val) {
                ans = mid;
                r = mid - 1;
            } else { // row[mid] >= val
                l = mid + 1;
            }
        }
        return ans;
    }

    private int countGreater(int[] row, int val) {
        int l = 0, r = row.length - 1, ans = row.length;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (row[mid] <= val) {
                ans = mid;
                r = mid - 1;
            } else { // row[mid] > val
                l = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
1. **Preprocessing**:
   - Sort each row of the `grid` in descending order: `O(n*m*log m)`.
   - Compute prefix sums for each sorted row to quickly find the sum of the top `x` elements: `O(n*m)`.
2. **Binary Search for Threshold**:
   - The key insight is that the number of elements we can pick is monotonic with respect to a minimum value threshold. If we can pick `C` elements with value `>= T`, we can also pick at least `C` elements with value `>= T-1`.
   - We can binary search for the optimal threshold value `T`. This `T` will be the value of the `k`-th element we pick (or 0 if we pick fewer than `k` elements).
   - The search space for `T` is `[0, 10^5 + 1]`.
   - For each `mid` value in the binary search, we have a `check(mid)` function that counts how many elements with value `>= mid` can be picked across all rows while respecting the `limits` array. This check can be done in `O(n*log m)` by using binary search on each sorted row.
   - We want to find the largest `T` such that `check(T) >= k`.
3. **Calculate Final Sum**:
   - Once the optimal threshold `T` is found, we can calculate the final sum.
   - First, sum up all elements that are strictly greater than `T`, respecting each row's limit. This can be done in `O(n*log m)` using the precomputed prefix sums.
   - Let the count of these elements be `elementsCount`.
   - We need to pick `k - elementsCount` more elements. Since `T` is our threshold, all these remaining elements will have the value `T`.
   - The final sum is `(sum of elements > T) + (k - elementsCount) * T`.
4. **Result**:
   - Return the calculated total sum.

# Solutions
### Java

```java
class Solution {
public
  long maxSum(int[][] grid, int[] limits, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int n = grid.length;
    for (int i = 0; i < n; ++i) {
      int[] nums = grid[i];
      int limit = limits[i];
      Arrays.sort(nums);
      for (int j = 0; j < limit; ++j) {
        pq.offer(nums[nums.length - j - 1]);
        if (pq.size() > k) {
          pq.poll();
        }
      }
    }
    long ans = 0;
    for (int x : pq) {
      ans += x;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxSum(vector<vector<int>> &grid, vector<int> &limits, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int n = grid.size();
    for (int i = 0; i < n; ++i) {
      vector<int> nums = grid[i];
      int limit = limits[i];
      ranges ::sort(nums);
      for (int j = 0; j < limit; ++j) {
        pq.push(nums[nums.size() - j - 1]);
        if (pq.size() > k) {
          pq.pop();
        }
      }
    }
    long long ans = 0;
    while (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int: pq = [] for nums, limit in zip(grid, limits): nums . sort() for _ in range(limit): heappush(pq, nums . pop()) if len(pq) > k: heappop(pq) return sum(pq)

```