Maximum sum with at most k elements

Array Greedy Sorting Heap (Priority Queue) Matrix

60.6% acceptance

Feb 25, 2026

109

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum(grid: Vec<Vec<i32>>, limits: Vec<i32>, k: i32) -> i64 {
    let mut all: Vec<i32> = grid.iter().zip(limits.iter()).flat_map(|(row, &lim)| {
      let mut r = row.clone(); r.sort_unstable_by(|a,b| b.cmp(a));
      r.into_iter().take(lim as usize)
    }).collect();
    all.sort_unstable_by(|a,b| b.cmp(a));
    all.iter().take(k as usize).map(|&x| x as i64).sum()
  }
}