LeetCode 3462 - Maximum Sum With at Most K Elements

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue), Matrix

Solution

Problem Understanding

We are given a matrix grid, where each row contains a collection of values that can potentially be selected. We are also given an array limits, where limits[i] specifies the maximum number of elements that may be chosen from row i.

The goal is to select at most k elements in total while respecting every row's selection limit. Among all valid selections, we want the largest possible sum.

A useful way to think about the problem is that each row contributes a limited number of "eligible" elements. Once those row-specific restrictions are satisfied, we must determine which elements should actually be included in the final selection so that the total sum is maximized.

The constraints are important:

There can be up to 500 rows.
Each row can contain up to 500 elements.
Therefore, the matrix can contain as many as 250,000 values.
All values are non-negative (0 <= grid[i][j] <= 100000).

The fact that all values are non-negative is extremely important. Since adding a non-negative value can never decrease the sum, the optimal solution will always favor larger values whenever they are available.

Some important edge cases include:

k = 0, where no elements can be selected.
Some rows may have limits[i] = 0, meaning that row contributes nothing.
k may be smaller than the total number of allowable elements.
k may equal the total allowable capacity.
Rows may contain many duplicate values.
Rows may contain only zeros.

Because all values are non-negative and the constraints are fairly large, we need a solution significantly better than exploring combinations of selections.

Approaches

Brute Force

A brute force solution would consider every valid subset of matrix elements that satisfies both:

The total number of chosen elements is at most k.
The number chosen from row i does not exceed limits[i].

For each valid selection, we would compute its sum and keep the maximum.

This approach is correct because it explicitly checks every possible valid answer. However, it is completely impractical. Even a matrix containing a few dozen elements already produces an astronomical number of subsets. With up to 250,000 elements, exhaustive search is impossible.

Key Insight

The row limits create an important observation.

Suppose a row is:

[8, 3, 6, 2]

and the row limit is 2.

If we are ever going to take elements from this row, there is never a reason to consider 3 or 2 before considering 8 and 6. Any solution that selects 3 while not selecting 6 can be improved by replacing 3 with 6.

Therefore:

For each row, only the largest limits[i] values can ever appear in an optimal solution.
Every other value in that row is permanently irrelevant.

After extracting those eligible values from every row, the problem becomes much simpler:

From all eligible values across all rows, choose the largest k values.

Since every value is non-negative, selecting the largest available values always maximizes the sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all valid selections
Optimal	O(n * m log m + L log L)	O(L)	Keep only row-eligible values, then choose global top k

Here L = sum(limits).

Algorithm Walkthrough

Optimal Algorithm

Create an empty array called candidates.
Process each row independently.
Sort the current row in descending order.
Take only the first limits[i] values from that sorted row.

These are the only values from that row that could possibly belong to an optimal solution. Any value beyond that position can never outperform one of the larger values above it. 5. Append those selected row values to candidates. 6. After all rows have been processed, candidates contains every value that could potentially appear in an optimal answer. 7. Sort candidates in descending order. 8. Take the first k values from candidates. 9. Compute and return their sum.

Why it works

For any row, suppose an optimal solution contains a value that is not among the row's largest limits[i] elements. Since at most limits[i] elements may be selected from that row, there must exist a larger unused element in the same row. Replacing the smaller chosen value with that larger unused value increases or preserves the total sum while still satisfying the row limit. Therefore, every selected value in an optimal solution must come from the row's top limits[i] elements.

Once all rows are reduced to these eligible values, the remaining constraint disappears. We simply need the largest total sum using at most k elements. Since all values are non-negative, choosing the globally largest k eligible values is optimal.

Python Solution

from typing import List

class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
        candidates = []

        for row, limit in zip(grid, limits):
            row.sort(reverse=True)
            candidates.extend(row[:limit])

        candidates.sort(reverse=True)

        return sum(candidates[:k])

The implementation directly follows the algorithm.

For each row, we sort in descending order so that the largest values appear first. We then keep only the first limit values because every other value in that row can never contribute to an optimal solution.

All of these row-level candidates are collected into a single list. After processing every row, we sort that combined list in descending order and take the largest k values. Their sum is the maximum achievable answer.

The code is concise because the core observation eliminates the need for dynamic programming, backtracking, or complicated data structures.

Go Solution

import "sort"

func maxSum(grid [][]int, limits []int, k int) int64 {
	candidates := make([]int, 0)

	for i, row := range grid {
		sort.Slice(row, func(a, b int) bool {
			return row[a] > row[b]
		})

		limit := limits[i]
		for j := 0; j < limit; j++ {
			candidates = append(candidates, row[j])
		}
	}

	sort.Slice(candidates, func(i, j int) bool {
		return candidates[i] > candidates[j]
	})

	var ans int64 = 0
	for i := 0; i < k && i < len(candidates); i++ {
		ans += int64(candidates[i])
	}

	return ans
}

The Go implementation mirrors the Python approach.

One important difference is the return type. The required signature returns int64, which is safer because the sum can exceed the range of a 32-bit integer. The algorithm stores individual values as int but accumulates the final answer in an int64.

The sorting is performed using sort.Slice, which allows descending-order sorting with a custom comparator.

Worked Examples

Example 1

Input

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

Step 1: Process Row 0

Original Row	Sorted Desc	Limit	Kept Values
[1,2]	[2,1]	1	[2]

Candidates:

[2]

Step 2: Process Row 1

Original Row	Sorted Desc	Limit	Kept Values
[3,4]	[4,3]	2	[4,3]

Candidates:

[2,4,3]

Step 3: Sort Candidates

[4,3,2]

Step 4: Take Top k = 2

[4,3]

Sum:

4 + 3 = 7

Answer = 7

Example 2

Input

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

Step 1: Process Row 0

Original Row	Sorted Desc	Limit	Kept Values
[5,3,7]	[7,5,3]	2	[7,5]

Candidates:

[7,5]

Step 2: Process Row 1

Original Row	Sorted Desc	Limit	Kept Values
[8,2,6]	[8,6,2]	2	[8,6]

Candidates:

[7,5,8,6]

Step 3: Sort Candidates

[8,7,6,5]

Step 4: Take Top k = 3

[8,7,6]

Sum:

8 + 7 + 6 = 21

Answer = 21

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m log m + L log L)	Sort every row, then sort all eligible values
Space	O(L)	Store all eligible values

Here L = sum(limits).

Each row of length m is sorted once, costing O(m log m) per row. Across all rows this becomes O(n * m log m).

After extracting eligible values, we sort the combined candidate list containing L elements, which costs O(L log L).

The additional memory usage comes from storing those L candidate values.

Test Cases

from typing import List

s = Solution()

assert s.maxSum([[1, 2], [3, 4]], [1, 2], 2) == 7          # example 1

assert s.maxSum([[5, 3, 7], [8, 2, 6]], [2, 2], 3) == 21  # example 2

assert s.maxSum([[1, 2, 3]], [3], 0) == 0                 # k = 0

assert s.maxSum([[1, 2, 3]], [0], 0) == 0                 # row limit zero

assert s.maxSum([[10]], [1], 1) == 10                     # single element

assert s.maxSum([[10]], [0], 0) == 0                      # single element not allowed

assert s.maxSum([[5, 4, 3]], [2], 2) == 9                 # take top two

assert s.maxSum([[5, 4, 3]], [1], 1) == 5                 # limit restricts choices

assert s.maxSum([[0, 0], [0, 0]], [2, 2], 3) == 0         # all zeros

assert s.maxSum([[8, 1], [7, 6]], [1, 1], 2) == 15        # row limits on both rows

assert s.maxSum([[9, 8], [7, 6]], [2, 2], 4) == 30        # use all eligible values

assert s.maxSum([[100, 1, 1], [99, 98, 97]], [1, 2], 3) == 297  # mixed limits

assert s.maxSum([[5, 5, 5], [5, 5]], [2, 1], 3) == 15     # duplicates

assert s.maxSum([[1, 100], [50, 60]], [1, 1], 1) == 100   # k smaller than capacity

Test Summary

Test	Why
Example 1	Verifies basic functionality
Example 2	Verifies selection across multiple rows
k = 0	No elements may be selected
limit = 0	Entire row unavailable
Single allowed element	Smallest non-trivial input
Single disallowed element	Limit prevents selection
One row, top two	Basic sorting behavior
One row, limit one	Row restriction enforced
All zeros	Non-negative edge case
Limits on multiple rows	Checks row constraints
Use all candidates	Capacity equals available values
Mixed limits	Validates optimal global selection
Duplicate values	Handles ties correctly
Small k	Global top-k behavior

Edge Cases

k Equals Zero

When k = 0, the answer must be zero regardless of the matrix contents. A buggy implementation might still attempt to select values or access elements unnecessarily. The implementation handles this naturally because candidates[:0] is an empty list and its sum is zero.

Rows With Zero Limit

A row may have limits[i] = 0, meaning no values can be selected from that row. Such rows should contribute nothing to the candidate pool. The implementation correctly handles this because row[:0] produces an empty slice and no values are added.

k Smaller Than Total Available Capacity

There may be many eligible values but only a few selections allowed. For example:

grid = [[100, 90], [80, 70]]
limits = [2, 2]
k = 1

Even though four values are eligible, only one may be chosen. The algorithm handles this by globally sorting all candidates and taking only the largest k values.

Duplicate Values

Multiple rows may contain identical values. Some incorrect greedy implementations accidentally depend on uniqueness. This solution relies only on ordering and counts, so duplicates are handled correctly without any special logic.

All Values Are Zero

Because the problem allows zero-valued elements, an implementation must not assume every selected value increases the sum. The algorithm still works correctly because sorting and selecting the largest values remains valid, and the final sum naturally evaluates to zero when appropriate.