#3462

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Sum With at Most K Elements

Find the maximum sum by selecting at most k elements from a 2D matrix respecting per-row limits using a greedy strategy.

array greedy sorting heap priority queue matrix

Problem Statement

You are given a 2D integer matrix grid of size n x m, an integer array limits of length n, and an integer k. Your task is to select at most k elements from the grid such that no more than limits[i] elements are chosen from row i.

Return the maximum sum achievable under these constraints. For example, given grid = [[1,2],[3,4]], limits = [1,2], and k = 2, the largest sum is 7 by picking 3 and 4.

Examples

Example 1

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

Output: 7

Example 2

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

Output: 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))

Solution Approach

Sort Each Row Descending

Sort each row of the matrix in descending order so the largest elements are first. This step sets up the greedy selection and simplifies top-value extraction per row limit.

Use Priority Queue for Global Selection

Push the top candidates from each row into a max-heap to efficiently pick the next largest element across all rows. Repeat until k elements are selected or no candidates remain.

Validate Row Limits

Track how many elements have been taken from each row to ensure limits[i] are not exceeded. Only push or select elements if the row limit allows, maintaining the invariant for correctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n m log m) for sorting plus O(k log n) for heap operations. Space complexity is O(n m) for the sorted rows and O(n) for the heap tracking candidates.

What Interviewers Usually Probe

Candidate quickly identifies greedy strategy for selecting maximum elements.
Explains how row limits affect element selection and sum calculation.
Uses sorting and heap to optimize selection while respecting constraints.

Common Pitfalls or Variants

Common pitfalls

Forgetting to enforce row limits and selecting more elements than allowed from a row.
Not handling k less than total selectable elements, leading to incorrect sum.
Ignoring the need to sort rows, which can lead to suboptimal greedy picks.

Follow-up variants

Allow negative integers in the grid, requiring careful top-k selection with possible pruning.
Change the problem to select exactly k elements, which may require dynamic programming.
Use a 3D matrix with per-layer limits, extending the greedy plus invariant validation pattern.

FAQ

What is the main pattern used in Maximum Sum With at Most K Elements?

The main pattern is greedy choice plus invariant validation, ensuring each row limit is respected while maximizing the sum.

How do I handle row limits efficiently?

Sort each row descending and select only the top limits[i] elements, using a heap to combine rows efficiently.

What if k is smaller than the total available elements?

Use a max-heap to pick the k largest valid elements across all rows, always checking row limits.

Can elements be negative?

Yes, negative numbers can occur. The greedy strategy still works, but skip elements that would reduce the sum.

Is sorting necessary for this problem?

Yes, sorting each row descending is crucial to ensure the greedy selection chooses the largest available elements per row.

terminal

Solution

Solution 1: Greedy + Priority Queue (Min-Heap)

We can use a priority queue (min-heap) $\textit{pq}$ to maintain the largest $k$ elements.

1

2

3

4

5

6

7

8

9

10

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)

Continue Practicing

#2931 maximum spending after buying items #3362 zero array transformation iii #3572 maximize ysum by picking a triplet of distinct xvalues