# Sum in a Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/sum-in-a-matrix
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## Problem
You are given a **0-indexed** 2D integer array `nums`. Initially, your score is `0`. Perform the following operations until the matrix becomes empty:

1. From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
2. Identify the highest number amongst all those removed in step 1\. Add that number to your **score**.

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 <= 300`
* `1 <= nums[i].length <= 500`
* `0 <= nums[i][j] <= 103`

# Approaches
## Brute-Force Simulation with Removal
This approach directly simulates the process described in the problem statement. It repeatedly finds the largest element in each row, removes it, and then finds the maximum among the removed elements to add to the score. This continues until all rows are empty.
**Time:** O(m * n^2), where `m` is the number of rows and `n` is the number of columns. The main loop runs `n` times. Inside, we iterate through `m` rows. For each row, finding the maximum (`Collections.max`) and removing it (`list.remove`) both take time proportional to the current row size. The row size decreases from `n` to 1. The total work for one row over all steps is O(n^2). For `m` rows, the total time is `O(m * n^2)`. · **Space:** O(m * n). We create a new `List<List<Integer>>` to store a copy of the matrix, which requires space proportional to the size of the original matrix.
**Pros:** Conceptually simple as it directly models the problem's description.
**Cons:** Highly inefficient due to repeated linear scans to find the maximum element in each row.; The `remove` operation on an `ArrayList` is also costly (O(n)).; Requires significant extra space to create a mutable copy of the matrix.
### Explanation
To facilitate the removal of elements, we first convert the input 2D array `nums` into a `List` of `List`s of `Integer`s. This allows for dynamic resizing and element removal.

We then enter a loop that continues as long as the rows (the inner lists) are not empty. In each iteration of the loop, we simulate one step of the process:
1.  Initialize a variable `maxOfRemoved` to track the maximum element found in the current step.
2.  Iterate through each row (list). For each row, find its maximum element. This requires a linear scan of the current elements in that row.
3.  Remove one instance of this maximum element from the row list. The `remove(Object)` method of `ArrayList` is suitable here.
4.  Update `maxOfRemoved` with the maximum from the current row if it's larger.
5.  After processing all rows, add `maxOfRemoved` to the total `score`.

The loop terminates when all rows become empty, which happens after a number of iterations equal to the original number of columns. The final `score` is then returned.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int matrixSum(int[][] nums) {
        int m = nums.length;
        if (m == 0) return 0;
        int n = nums[0].length;
        
        List<List<Integer>> matrix = new ArrayList<>();
        for (int[] row : nums) {
            List<Integer> newRow = new ArrayList<>();
            for (int val : row) {
                newRow.add(val);
            }
            matrix.add(newRow);
        }

        int score = 0;
        for (int k = 0; k < n; k++) { // Loop n times for n columns
            int maxInStep = 0;
            for (int i = 0; i < m; i++) {
                List<Integer> currentRow = matrix.get(i);
                int rowMax = Collections.max(currentRow);
                currentRow.remove(Integer.valueOf(rowMax));
                maxInStep = Math.max(maxInStep, rowMax);
            }
            score += maxInStep;
        }
        return score;
    }
}
```
### Algorithm
*   Initialize `score = 0`.
*   Convert the `int[][]` into a `List<List<Integer>>` for easier element removal.
*   Loop `n` times, where `n` is the number of columns.
*   In each iteration (step):
    *   Initialize `maxInStep = 0`.
    *   For each row in the list of lists:
        *   Find the maximum element in the current row.
        *   Remove one occurrence of that maximum element from the row.
        *   Update `maxInStep` with the maximum element found so far in this step.
    *   Add `maxInStep` to the total `score`.
*   Return `score`.

## Sort Each Row and Iterate by Column
A much more efficient approach is to first sort each row of the matrix. Once sorted, the problem simplifies significantly. The largest elements of all rows are in the last column, the second-largest are in the second-to-last column, and so on. We can then iterate column by column to find the required maximums for each step.
**Time:** O(m * n * log n). The dominant part of the algorithm is sorting. We have `m` rows, and sorting each row of size `n` takes O(n * log n) time. Thus, the total time for sorting is O(m * n * log n). The subsequent step of iterating through the sorted matrix to sum the column-wise maximums takes O(m * n) time. The overall complexity is O(m * n * log n + m * n), which simplifies to O(m * n * log n). · **Space:** O(log n) or O(n) in the worst case. This approach modifies the input matrix in-place. The space complexity is determined by the space used by the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which requires O(log n) space on average for the recursion stack. In the worst case, it can degrade to O(n) space.
**Pros:** Significantly more efficient than the brute-force simulation.; The logic is clean and easy to implement once the sorting insight is realized.; Space-efficient if in-place modification of the input is allowed.
**Cons:** Modifies the original input matrix. A copy would be needed if the original data must be preserved, which would increase space complexity.
### Explanation
The core insight is that the sequence of numbers removed from a single row is always in non-increasing order. For example, we first remove the largest, then the largest of what's left (which is the original second-largest), and so on. This is equivalent to taking the elements of the sorted row in descending order.

Therefore, we can pre-process the matrix by sorting each row. We can use `Arrays.sort()` on each row `nums[i]`. Let's sort them in ascending order for convenience.

After sorting, `nums[i][n-1]` is the largest element of row `i`, `nums[i][n-2]` is the second largest, and so on.

The first operation in the problem corresponds to finding the maximum among all `nums[i][n-1]`. The second operation corresponds to finding the maximum among all `nums[i][n-2]`, and so on.

We can implement this by iterating through the columns from `j = n-1` down to `0`. In each iteration `j`, we find the maximum value in that column (`max(nums[0][j], nums[1][j], ..., nums[m-1][j])`) and add it to our score. The sum is commutative, so iterating columns from `j=0` to `n-1` yields the same result and is simpler to write.

```java
import java.util.Arrays;

class Solution {
    public int matrixSum(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        int score = 0;

        // Step 1: Sort each row
        for (int i = 0; i < m; i++) {
            Arrays.sort(nums[i]);
        }

        // Step 2: Iterate through columns and find the max in each column
        for (int j = 0; j < n; j++) {
            int maxInColumn = 0;
            for (int i = 0; i < m; i++) {
                if (nums[i][j] > maxInColumn) {
                    maxInColumn = nums[i][j];
                }
            }
            // Add the max of the column to the score
            score += maxInColumn;
        }

        return score;
    }
}
```
### Algorithm
*   Initialize `score = 0`.
*   Iterate through each row of the input matrix `nums`.
*   For each row, sort its elements in non-decreasing order using `Arrays.sort()`.
*   After all rows are sorted, iterate through the columns from `j = 0` to `n-1` (where `n` is the number of columns).
*   For each column `j`:
    *   Initialize `maxInColumn = 0`.
    *   Iterate through each row `i` from `0` to `m-1` (where `m` is the number of rows).
    *   Update `maxInColumn = Math.max(maxInColumn, nums[i][j])`.
    *   After checking all rows, `maxInColumn` will hold the maximum value in the current column `j`.
    *   Add `maxInColumn` to the total `score`.
*   Return the final `score`.

# Solutions
### Java

```java
class Solution {
public
  int matrixSum(int[][] nums) {
    for (var row : nums) {
      Arrays.sort(row);
    }
    int ans = 0;
    for (int j = 0; j < nums[0].length; ++j) {
      int mx = 0;
      for (var row : nums) {
        mx = Math.max(mx, row[j]);
      }
      ans += mx;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int matrixSum(vector<vector<int>> &nums) {
    for (auto &row : nums) {
      sort(row.begin(), row.end());
    }
    int ans = 0;
    for (int j = 0; j < nums[0].size(); ++j) {
      int mx = 0;
      for (auto &row : nums) {
        mx = max(mx, row[j]);
      }
      ans += mx;
    }
    return ans;
  }
};

```

### Python

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

```