#2679

Medium

LeetCode Problem Workspace

Sum in a Matrix

Calculate the maximum score by repeatedly removing the largest elements from each row of a 2D matrix efficiently using sorting techniques.

array sorting heap priority queue matrix simulation

Problem Statement

You are given a 0-indexed 2D integer array nums. Your goal is to maximize your score by performing the following operations until the matrix is empty: in each operation, remove the largest number from every row and add the maximum of these removed numbers to your score.

Return the total score after all rows have been exhausted. For example, given nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]], the sequence of maximum removals yields a final score of 15, while for nums = [[1]] the score is 1.

Examples

Example 1

Input: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]

Output: 15

In the first operation, we remove 7, 6, 6, and 3. We then add 7 to our score. Next, we remove 2, 4, 5, and 2. We add 5 to our score. Lastly, we remove 1, 2, 3, and 1. We add 3 to our score. Thus, our final score is 7 + 5 + 3 = 15.

Example 2

Input: nums = [[1]]

Output: 1

We remove 1 and add it to the answer. We return 1.

Constraints

1 <= nums.length <= 300
1 <= nums[i].length <= 500
0 <= nums[i][j] <= 103

Solution Approach

Sort Rows in Descending Order

Sort each row of the matrix in descending order to make it efficient to access the largest number during each operation. This setup allows constant-time removal of the row maximums.

Iteratively Remove Maximums

In each iteration, remove the first element from each row, collect these values, and add the maximum among them to the running score. Continue until all rows are empty, ensuring no element is skipped.

Optimize with Heaps for Larger Matrices

For very large matrices, use a heap or priority queue to maintain the current maximum across all rows dynamically. This reduces repeated full scans for the maximum at each operation and handles memory efficiently.

Complexity Analysis

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

Sorting each row takes O(n * m log m) time, where n is the number of rows and m is the maximum row length. Removing elements iteratively and tracking row maxima adds additional O(n * m) time. Space is O(1) extra if modifying in place, or O(n * m) if using a copy for sorting.

What Interviewers Usually Probe

Focus on sorting rows efficiently before starting iterative removal.
Consider using a priority queue if the interviewer hints at optimizing repeated max searches.
Be ready to explain why row-wise sorting ensures the maximum score.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort rows in descending order can lead to suboptimal score calculations.
Ignoring empty rows when collecting maximums may cause index errors.
Using nested loops to find the maximum in every iteration is inefficient for large matrices.

Follow-up variants

Compute the minimum score by always adding the minimum among removed row elements instead of the maximum.
Allow diagonal or column-wise removals instead of only row-wise, changing the iteration pattern.
Handle dynamic matrices where new rows can be appended during operations, requiring online maximum tracking.

FAQ

What is the core strategy to solve Sum in a Matrix efficiently?

Sort each row in descending order and iteratively remove the first element from each row, adding the maximum among them to the score.

Can I use a heap to optimize this problem?

Yes, maintaining the current maximum of row heads in a heap reduces repeated scanning and speeds up large inputs.

Why does row-wise sorting matter in Sum in a Matrix?

Sorting ensures that each operation correctly identifies the largest available numbers per row, which maximizes the final score.

What should I be careful about with empty rows?

Always check for empty rows when removing elements to avoid index errors and incorrect maximum selection.

How does this problem illustrate the Array plus Sorting pattern?

It combines row-wise array manipulation with sorting to efficiently track and compute the maximum values for score accumulation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        for row in nums:
            row.sort()
        return sum(map(max, zip(*nums)))

Continue Practicing

#2500 delete greatest value in each row #2593 find score of an array after marking all elements #2503 maximum number of points from grid queries