Sum in a Matrix

Med

#2428Time: 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.

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)Matrix

Prompt

You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:

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.
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] <= 10³

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

To facilitate the removal of elements, we first convert the input 2D array nums into a List of Lists of Integers. 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:

Initialize a variable maxOfRemoved to track the maximum element found in the current step.
Iterate through each row (list). For each row, find its maximum element. This requires a linear scan of the current elements in that row.
Remove one instance of this maximum element from the row list. The remove(Object) method of ArrayList is suitable here.
Update maxOfRemoved with the maximum from the current row if it's larger.
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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int matrixSum(int[][] nums) {7        int m = nums.length;8        if (m == 0) return 0;9        int n = nums[0].length;10        11        List<List<Integer>> matrix = new ArrayList<>();12        for (int[] row : nums) {13            List<Integer> newRow = new ArrayList<>();14            for (int val : row) {15                newRow.add(val);16            }17            matrix.add(newRow);18        }19 20        int score = 0;21        for (int k = 0; k < n; k++) { // Loop n times for n columns22            int maxInStep = 0;23            for (int i = 0; i < m; i++) {24                List<Integer> currentRow = matrix.get(i);25                int rowMax = Collections.max(currentRow);26                currentRow.remove(Integer.valueOf(rowMax));27                maxInStep = Math.max(maxInStep, rowMax);28            }29            score += maxInStep;30        }31        return score;32    }33}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public int matrixSum(int[][] nums) {5        int m = nums.length;6        int n = nums[0].length;7        int score = 0;8 9        // Step 1: Sort each row10        for (int i = 0; i < m; i++) {11            Arrays.sort(nums[i]);12        }13 14        // Step 2: Iterate through columns and find the max in each column15        for (int j = 0; j < n; j++) {16            int maxInColumn = 0;17            for (int i = 0; i < m; i++) {18                if (nums[i][j] > maxInColumn) {19                    maxInColumn = nums[i][j];20                }21            }22            // Add the max of the column to the score23            score += maxInColumn;24        }25 26        return score;27    }28}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int matrixSum(int[][] nums) {4    for (var row : nums) {5      Arrays.sort(row);6    }7    int ans = 0;8    for (int j = 0; j < nums[0].length; ++j) {9      int mx = 0;10      for (var row : nums) {11        mx = Math.max(mx, row[j]);12      }13      ans += mx;14    }15    return ans;16  }17}

1class Solution {2public:3  int matrixSum(vector<vector<int>> &nums) {4    for (auto &row : nums) {5      sort(row.begin(), row.end());6    }7    int ans = 0;8    for (int j = 0; j < nums[0].size(); ++j) {9      int mx = 0;10      for (auto &row : nums) {11        mx = max(mx, row[j]);12      }13      ans += mx;14    }15    return ans;16  }17};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem