How to Solve Maximum Sum With at Most K Elements

This problem requires maximizing the sum by picking at most k elements across rows while respecting individual row limits. The optimal approach is to sort each row in descending order, then select the top values according to the limits while maintaining a running total. By carefully combining the largest available elements across all rows, you can efficiently reach the maximum sum without violating any row constraints.

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

Time complexity is O(nm log m) for sorting plus O(k log n) for heap operations. Space complexity is O(nm) 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.

How GhostInterview Helps

• GhostInterview guides selection of top elements per row and manages heap operations for global maximum efficiently.
• It ensures row limit invariants are maintained and flags selections that would exceed constraints.
• It provides step-by-step computation of running sum, verifying correctness after each element choice.

Topic Pages

• Array
• Greedy
• Sorting
• Heap (Priority Queue)
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.