Maximum Sum With at Most K Elements

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

1
2
3
4
5


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

1
2
3
4
5
6


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] <= 10^5
0 <= limits[i] <= m
0 <= k <= min(n * m, sum(limits))

Examples

Solution

Method 1 – Greedy with Min-Heap

Intuition

To maximize the sum, we want to pick the largest possible elements from the matrix, but we must respect the per-row limits and the overall limit of k elements. We can collect the allowed elements from each row, sort them, and pick the top k.

Approach

For each row, sort the elements in descending order and take up to limits[i] elements.
Collect all selected elements from all rows into a single list.
Sort the combined list in descending order.
Pick the top k elements and sum them for the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int maxSumWithAtMostKElements(vector<vector<int>>& grid, vector<int>& limits, int k) {
        vector<int> pool;
        for (int i = 0; i < grid.size(); ++i) {
            auto row = grid[i];
            sort(row.rbegin(), row.rend());
            for (int j = 0; j < min((int)row.size(), limits[i]); ++j)
                pool.push_back(row[j]);
        }
        sort(pool.rbegin(), pool.rend());
        int ans = 0;
        for (int i = 0; i < min(k, (int)pool.size()); ++i)
            ans += pool[i];
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import "sort"
func maxSumWithAtMostKElements(grid [][]int, limits []int, k int) int {
    pool := []int{}
    for i, row := range grid {
        r := append([]int{}, row...)
        sort.Sort(sort.Reverse(sort.IntSlice(r)))
        for j := 0; j < limits[i] && j < len(r); j++ {
            pool = append(pool, r[j])
        }
    }
    sort.Sort(sort.Reverse(sort.IntSlice(pool)))
    ans := 0
    for i := 0; i < k && i < len(pool); i++ {
        ans += pool[i]
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    public int maxSumWithAtMostKElements(int[][] grid, int[] limits, int k) {
        List<Integer> pool = new ArrayList<>();
        for (int i = 0; i < grid.length; ++i) {
            int[] row = grid[i].clone();
            Arrays.sort(row);
            for (int j = row.length - 1; j >= row.length - Math.min(row.length, limits[i]); --j)
                pool.add(row[j]);
        }
        pool.sort(Collections.reverseOrder());
        int ans = 0;
        for (int i = 0; i < Math.min(k, pool.size()); ++i)
            ans += pool.get(i);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun maxSumWithAtMostKElements(grid: Array<IntArray>, limits: IntArray, k: Int): Int {
        val pool = mutableListOf<Int>()
        for (i in grid.indices) {
            val row = grid[i].sortedDescending()
            for (j in 0 until minOf(row.size, limits[i]))
                pool.add(row[j])
        }
        val topK = pool.sortedDescending().take(k)
        return topK.sum()
    }
}

1
2
3
4
5
6
7
8


class Solution:
    def maxSumWithAtMostKElements(self, grid: list[list[int]], limits: list[int], k: int) -> int:
        pool: list[int] = []
        for i, row in enumerate(grid):
            top = sorted(row, reverse=True)[:limits[i]]
            pool.extend(top)
        pool.sort(reverse=True)
        return sum(pool[:k])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


impl Solution {
    pub fn max_sum_with_at_most_k_elements(grid: Vec<Vec<i32>>, limits: Vec<i32>, k: i32) -> i32 {
        let mut pool = vec![];
        for (i, row) in grid.iter().enumerate() {
            let mut r = row.clone();
            r.sort_by(|a, b| b.cmp(a));
            for j in 0..r.len().min(limits[i] as usize) {
                pool.push(r[j]);
            }
        }
        pool.sort_by(|a, b| b.cmp(a));
        pool.iter().take(k as usize).sum()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
    maxSumWithAtMostKElements(grid: number[][], limits: number[], k: number): number {
        let pool: number[] = [];
        for (let i = 0; i < grid.length; ++i) {
            let row = [...grid[i]].sort((a, b) => b - a);
            pool.push(...row.slice(0, limits[i]));
        }
        pool.sort((a, b) => b - a);
        return pool.slice(0, k).reduce((a, b) => a + b, 0);
    }
}

Complexity

⏰ Time complexity: O(nm log nm), where n and m are the grid dimensions. Sorting each row and the pool dominates.
🧺 Space complexity: O(nm), for the pool of selected elements.

Problem#

Example 1#

Example 2#

Constraints#

Examples#

Solution#

Method 1 – Greedy with Min-Heap#

Intuition#

Approach#

Code#

Complexity#