problemmediumalgorithmsleetcode-3462leetcode 3462leetcode3462

Maximum Sum With at Most K Elements

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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.

Examples

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

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

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

Code

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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()
    }
}
Python
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])
Rust
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()
    }
}
TypeScript
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.

Comments