LeetCode 2679 - Sum in a Matrix

Difficulty: 🟡 Medium
Topics: Array, Sorting, Heap (Priority Queue), Matrix, Simulation

Solution

Problem Understanding

The problem gives us a 2D integer matrix nums. Each row contains several integers, and we repeatedly perform a special removal process until every element has been removed.

During each operation, we do two things:

From every row, remove the largest remaining element.
Among all removed elements from this round, take the maximum value and add it to the total score.

We continue this process until the matrix is empty, then return the accumulated score.

The important observation is that every row contributes exactly one element during each round. Since all rows have the same number of columns in the examples and constraints, after enough rounds every element will eventually be removed.

For example, consider:

[[7,2,1],
 [6,4,2],
 [6,5,3],
 [3,2,1]]

In the first round:

Remove largest from each row:
7
6
6
3
Maximum among removed values is 7
Score becomes 7

In the second round:

Remaining rows:
[2,1]
[4,2]
[5,3]
[2,1]
Remove:
2
4
5
2
Maximum is 5
Score becomes 12

In the final round:

Remove:
1
2
3
1
Maximum is 3
Final score becomes 15

The constraints are important:

Up to 300 rows
Up to 500 columns
Values up to 1000

The total number of elements can reach 300 × 500 = 150,000, so we need something reasonably efficient. A naive simulation that repeatedly searches for maximum values in every row could become unnecessarily expensive.

Several edge cases are important:

A matrix containing only one element
Rows with duplicate values
Rows already sorted or completely unsorted
All values being equal
Large matrices where repeated maximum searches would be costly

The problem guarantees valid non-empty input, so we do not need to handle empty matrices.

Approaches

Brute Force Approach

A direct simulation approach would repeatedly perform the operations exactly as described.

For each round:

Scan every row to find its current maximum value.
Remove that value from the row.
Track the largest removed value across all rows.
Add it to the score.

This works correctly because it follows the problem statement literally.

However, it is inefficient because finding and removing the maximum from an unsorted row requires scanning the entire row each time. If a row has n elements, we perform scans of size n, then n-1, then n-2, and so on.

For one row, this becomes:

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

Across all rows, the complexity becomes too large for the constraints.

Optimal Approach

The key insight is that the removal order is completely determined by sorting each row.

If we sort each row in ascending order:

[1,2,7]
[2,4,6]
[3,5,6]
[1,2,3]

Then the largest element of each row is always at the end.

More importantly, during each round we are effectively comparing elements with the same relative rank from each row:

Largest elements
Second largest elements
Third largest elements
And so on

After sorting, we can simply process column by column.

For each column index:

Take the maximum value among all rows at that index.
Add it to the score.

This avoids repeated maximum searches and removals entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n²)	O(1)	Repeatedly scans rows to find and remove maximum values
Optimal	O(m × n log n)	O(1) or O(log n) depending on sorting	Sorts rows once, then processes columns efficiently

Where:

m = number of rows
n = number of columns

Algorithm Walkthrough

Sort every row in ascending order.

Sorting transforms the repeated "remove largest element" operation into a predictable structure. After sorting, the largest element of a row is at the last index, the second largest is at the second-to-last index, and so on. 2. Initialize a variable score = 0.

This variable stores the cumulative answer. 3. Iterate through each column index from left to right.

Since rows are sorted in ascending order, elements in the same column represent values with the same relative rank across rows. 4. For the current column, find the maximum value among all rows.

This simulates the value added during that round of removals. 5. Add this maximum value to the score.

The problem states that after removing one value from every row, we add the largest removed value to the total score. 6. Continue until all columns have been processed.

Every column corresponds to one complete removal round. 7. Return the final score.

Why it works

Sorting each row preserves the exact removal order that would occur during simulation. The largest element is removed first, the second largest second, and so on.

After sorting, all elements in column j correspond to elements removed during the same round. Taking the maximum value in that column exactly matches the score contribution defined by the problem.

Therefore, processing sorted columns produces the same result as the original simulation.

Python Solution

from typing import List

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        # Sort every row in ascending order
        for row in nums:
            row.sort()

        rows = len(nums)
        cols = len(nums[0])

        score = 0

        # Process each column
        for col in range(cols):
            current_max = 0

            for row in range(rows):
                current_max = max(current_max, nums[row][col])

            score += current_max

        return score

The implementation begins by sorting every row. This preprocessing step is the key optimization because it converts repeated maximum removals into simple column traversal.

Next, we determine the number of rows and columns. The matrix dimensions are needed for iteration.

The outer loop processes columns one at a time. Each column represents one removal round after sorting.

Inside the loop, we compute the maximum value among all rows for the current column. This simulates selecting the largest removed value during that round.

Finally, we add the column maximum to the total score and return the result after all columns are processed.

Go Solution

package main

import "sort"

func matrixSum(nums [][]int) int {
    // Sort each row
    for _, row := range nums {
        sort.Ints(row)
    }

    rows := len(nums)
    cols := len(nums[0])

    score := 0

    // Process columns
    for col := 0; col < cols; col++ {
        currentMax := 0

        for row := 0; row < rows; row++ {
            if nums[row][col] > currentMax {
                currentMax = nums[row][col]
            }
        }

        score += currentMax
    }

    return score
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go uses sort.Ints() to sort slices in place. Maximum tracking is implemented manually using an if condition rather than the built-in max() function available in Python.

Since all values are small and constraints are limited, standard int is sufficient and there is no overflow concern.

Worked Examples

Example 1

Input:

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

Step 1: Sort each row

Original Row	Sorted Row
[7,2,1]	[1,2,7]
[6,4,2]	[2,4,6]
[6,5,3]	[3,5,6]
[3,2,1]	[1,2,3]

Sorted matrix:

[
    [1,2,7],
    [2,4,6],
    [3,5,6],
    [1,2,3]
]

Step 2: Process columns

Column	Values	Column Maximum	Running Score
0	[1,2,3,1]	3	3
1	[2,4,5,2]	5	8
2	[7,6,6,3]	7	15

Final answer:

Example 2

Input:

[[1]]

Step 1: Sort rows

[[1]]

Step 2: Process columns

Column	Values	Column Maximum	Running Score
0	[1]	1	1

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n log n)	Each row is sorted independently
Space	O(1) auxiliary, ignoring sorting internals	Sorting is done in place

The dominant cost comes from sorting each row. If there are m rows and each row contains n elements, sorting one row costs O(n log n), leading to a total of O(m × n log n).

The column traversal afterward is only O(m × n), which is smaller than the sorting cost.

The algorithm modifies the input matrix in place, so additional memory usage is minimal aside from internal sorting overhead.

Test Cases

from typing import List

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        for row in nums:
            row.sort()

        score = 0

        for col in range(len(nums[0])):
            score += max(nums[row][col] for row in range(len(nums)))

        return score

sol = Solution()

assert sol.matrixSum([[7,2,1],[6,4,2],[6,5,3],[3,2,1]]) == 15  # provided example
assert sol.matrixSum([[1]]) == 1  # single element matrix
assert sol.matrixSum([[5,5],[5,5]]) == 10  # all values equal
assert sol.matrixSum([[1,2,3]]) == 6  # single row
assert sol.matrixSum([[1],[2],[3]]) == 3  # single column
assert sol.matrixSum([[10,1],[9,2],[8,3]]) == 19  # descending maxima
assert sol.matrixSum([[0,0,0],[0,0,0]]) == 0  # all zeros
assert sol.matrixSum([[3,1,2],[6,4,5]]) == 11  # unsorted rows
assert sol.matrixSum([[1000]*500 for _ in range(300)]) == 500000  # large stress case

Test Summary

Test	Why
`[[7,2,1],[6,4,2],[6,5,3],[3,2,1]]`	Verifies provided example
`[[1]]`	Smallest valid input
`[[5,5],[5,5]]`	Tests duplicate values
`[[1,2,3]]`	Single row behavior
`[[1],[2],[3]]`	Single column behavior
`[[10,1],[9,2],[8,3]]`	Verifies correct column maximum selection
`[[0,0,0],[0,0,0]]`	Tests zero values
`[[3,1,2],[6,4,5]]`	Confirms sorting logic
Large `300 × 500` matrix	Stress test near constraints

Edge Cases

Single Element Matrix

A matrix like [[1]] is the smallest possible valid input. A buggy implementation might incorrectly assume multiple rows or columns exist. This solution handles it naturally because sorting a single-element row is valid, and the column iteration runs exactly once.

Duplicate Values

Rows may contain repeated numbers, such as:

[[5,5],
 [5,5]]

The problem explicitly states that ties do not matter when removing the largest element. Sorting preserves duplicates correctly, and column maxima still represent the correct removal rounds.

Single Row Matrix

When there is only one row, every removed value automatically becomes the maximum for that round. For example:

[[1,2,3]]

After sorting, the algorithm processes columns directly and sums all values correctly.

Single Column Matrix

If each row contains only one value, there is only one removal round. The algorithm correctly computes the maximum value among all rows in that single column.

Completely Unsorted Input

Rows may appear in arbitrary order:

[[3,1,2],
 [6,4,5]]

The correctness of the algorithm depends on sorting first. Without sorting, columns would not correspond to removal rounds. By sorting every row before processing, the implementation guarantees correct alignment of removals.