You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:
Return the final score.
Example 1:
Input: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]] Output: 15 Explanation: 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 Explanation: We remove 1 and add it to the answer. We return 1.
Constraints:
1 <= nums.length <= 3001 <= nums[i].length <= 5000 <= nums[i][j] <= 103To solve #2679 Sum in a Matrix, the key idea is to simulate selecting the largest values column by column after organizing each row. First, sort every row of the matrix in non-decreasing order. After sorting, iterate from the last column to the first and pick the maximum value among all rows for that column. Add this value to the total sum. This works because sorting aligns each row so that larger values appear toward the right, allowing a consistent comparison across rows.
An alternative perspective uses a priority queue (heap) to repeatedly extract the largest remaining values per step, but sorting each row first keeps the implementation simpler and efficient. The simulation then becomes a straightforward column-wise scan.
The dominant cost comes from sorting each row, giving a time complexity of O(m * n log n) for an m x n matrix, while the additional space used is minimal aside from sorting overhead.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row Sorting + Column Simulation | O(m * n log n) | O(1) or O(log n) depending on sorting |
| Heap / Priority Queue Simulation | O(m * n log m) | O(m) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Sort the numbers in each row in decreasing order.
The answer is the summation of the max number in every column after sorting the rows.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, problems like this appear in coding interviews because they test sorting, matrix traversal, and simulation skills. Variations may also involve greedy selection or priority queues, which are common interview topics.
If each row is sorted first, the overall time complexity becomes O(m * n log n) for an m by n matrix. The remaining simulation step only scans columns and rows, which is linear relative to the matrix size.
Sorting arrays is the most practical structure used in this problem. However, a priority queue (max heap) can also be used to repeatedly extract the largest available values when simulating the process.
The optimal approach is to sort each row of the matrix and then simulate selecting values column by column. For each column from right to left, pick the maximum element among all rows and add it to the answer. This keeps the implementation simple while maintaining good efficiency.