How to Solve Sum in a Matrix

Start by sorting each row in descending order to ensure the largest elements are accessed first. In each operation, remove the first element from every row and add the maximum among them to the score. Repeat until all rows are empty, which guarantees the final score is maximized with minimal computation errors.

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

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.

How GhostInterview Helps

• GhostInterview automatically identifies the Array plus Sorting pattern and suggests sorting each row first to simplify operations.
• It highlights where iterating without a heap can cause slow performance, recommending priority queue optimization.
• The tool demonstrates the operation sequence step-by-step, ensuring the candidate understands the scoring logic clearly.

Topic Pages

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

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