Is Maximum Sum With at Most K Elements easy or hard?

Maximum Sum With at Most K Elements is typically classified as a Medium problem. The difficulty comes from combining two constraints: row-level limits and a global k selection. Recognizing that a heap can maintain the best k values efficiently is the main insight.

Maximum Sum With at Most K Elements Python/Java solution

The standard implementation iterates through rows, sorts each row in descending order, and pushes up to limits[i] values into a min-heap. If the heap size exceeds k, remove the smallest element. The same logic works in Python (heapq), Java (PriorityQueue), C++, Go, and TypeScript.

How to solve Maximum Sum With at Most K Elements in O(n log k)?

Iterate through each row of the matrix, sort the row in descending order, and consider only the first limits[i] elements. Push each value into a min-heap. If the heap grows larger than k, pop the smallest value. After processing all rows, sum the values remaining in the heap to get the maximum sum.

What is the best approach for Maximum Sum With at Most K Elements?

The optimal approach uses a greedy strategy with a min-heap (priority queue). For each row, take the largest values up to its limit and push them into a min-heap that stores only the best k elements seen so far. Whenever the heap size exceeds k, remove the smallest value. This guarantees the heap always contains the global top k values.

Is Maximum Sum With at Most K Elements asked at Google/Amazon/Meta?

Problems combining greedy selection with heaps frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of "top k elements" or "select k maximum values under constraints" are common interview patterns, making this problem good practice for priority queue usage.

What data structure is used in Maximum Sum With at Most K Elements?

A priority queue implemented as a min-heap is the main data structure. It maintains the current best k elements while scanning candidates. Sorting is also used to prioritize the largest values within each matrix row.

What is the time complexity of Maximum Sum With at Most K Elements?

The optimized solution runs in O(n log k) time, where n is the total number of candidate elements considered from all rows. Each element is inserted into a min-heap and may trigger one removal operation. The space complexity is O(k) because the heap never stores more than k elements.

Description Hints 2 Solution Video 10:00

3462. Maximum Sum With at Most K Elements

Medium60.6% acceptance2 companies

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 i^th row of grid does not exceed limits[i].

Return the maximum sum.

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

Asked at 2 companies

Amazon Microsoft

Topics

Array Greedy Heap (Priority Queue)Matrix Sorting

Hints open one at a time

Hint 1

Sort each row in descending order and extract the top limits[i] elements.

Hint 2

Use a max-heap to efficiently pick the largest k elements across all rows.

10:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,2],[3,4]]
[1,2]
2

Input

[[5,3,7],[8,2,6]]
[2,2]
3

Your code is saved on this device.Solution