Skip to main content
Talentd

Maximum Sum With at Most K Elements - Solution & Explanation

MediumArrayGreedySortingHeap (Priority Queue)7 min readAsked at: Amazon, Microsoft
Practice this problem

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. 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.

 

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

Approach Overview

Problem Overview: You get a matrix of numbers and an array limits where limits[i] tells how many elements you can take from row i. From all allowed picks, choose at most k elements so the total sum is maximum.

Approach 1: Collect Candidates + Full Sort (O(n log n) time, O(n) space)

Process each row independently. Sort the row in descending order and take the top limits[i] values because any smaller values would never help maximize the total. Add those values to a global list of candidates. Once all rows are processed, sort the candidate list in descending order and sum the largest k values. The logic is straightforward: reduce the matrix to only valid picks, then take the global top k. Time complexity becomes O(n log n) due to sorting the candidates, and space complexity is O(n) for storing them.

Approach 2: Greedy + Min-Heap (Priority Queue) (O(n log k) time, O(k) space)

This approach keeps only the best k elements seen so far. For each row, sort it descending and iterate over the first limits[i] values. Push each candidate into a min-heap. If the heap size exceeds k, remove the smallest element. The heap always stores the current top k values across all rows. The key insight: any element smaller than the smallest element in the heap cannot belong to the final answer once the heap is full. After processing all rows, sum the heap elements. This greedy strategy avoids sorting the entire candidate list and reduces work to O(n log k).

The solution combines ideas from greedy algorithms, heap (priority queue), and sorting. Each row is treated as an independent pool of values, but the heap enforces the global constraint of selecting only the best k values overall.

Recommended for interviews: The Greedy + Min-Heap approach. Interviewers want to see that you limit each row to its best candidates and then maintain a global top-k structure. The full sorting approach demonstrates correct reasoning, but the heap solution shows stronger optimization and familiarity with priority queues.

Solution

We can use a priority queue (min-heap) pq to maintain the largest k elements.

Traverse each row, sort the elements in each row, and then take the largest limit elements from each row and add them to pq. If the size of pq exceeds k, pop the top element of the heap.

Finally, sum the elements in pq.

The time complexity is O(n times m times (log m + log k)), and the space complexity is O(k). Here, n and m are the number of rows and columns of the matrix grid, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Collect Candidates + Full SortO(n log n)O(n)Simplest implementation when constraints are small and memory is not a concern
Greedy + Min-Heap (Priority Queue)O(n log k)O(k)Optimal approach when the candidate pool is large but only top k values matter

Video Solution

3462. Maximum Sum With at Most K Elements | Greedy • Aryan Mittal • 1,582 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Sum With at Most K Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays