Scale Engineer

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
ArrayHeap (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:

  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

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:

  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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem