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 finalscore.

Examples

Example 1

1
2
3

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

1
2
3

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^3

Solution

Method 1 – Sort Each Row and Simulate

Intuition

If we sort each row in ascending order, the largest numbers in each row will always be at the end. In each round, we remove the largest remaining number from each row, and the score for that round is the maximum among those numbers. Repeat until all columns are removed.

Approach

  1. Sort each row in ascending order.
  2. For each column from the last to the first:
    • Collect the largest remaining number from each row (i.e., the last element in each row).
    • The score for this round is the maximum of these numbers.
    • Add this score to the total.
  3. Return the total score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

import "sort"
func matrixSum(nums [][]int) int {
    m, n := len(nums), len(nums[0])
    for i := 0; i < m; i++ {
        sort.Ints(nums[i])
    }
    ans := 0
    for j := n-1; j >= 0; j-- {
        mx := 0
        for i := 0; i < m; i++ {
            if nums[i][j] > mx {
                mx = nums[i][j]
            }
        }
        ans += mx
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int matrixSum(int[][] nums) {
        int m = nums.length, n = nums[0].length, ans = 0;
        for (int[] row : nums) Arrays.sort(row);
        for (int j = n-1; j >= 0; j--) {
            int mx = 0;
            for (int i = 0; i < m; i++) mx = Math.max(mx, nums[i][j]);
            ans += mx;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun matrixSum(nums: Array<IntArray>): Int {
        val m = nums.size
        val n = nums[0].size
        for (row in nums) row.sort()
        var ans = 0
        for (j in n-1 downTo 0) {
            var mx = 0
            for (i in 0 until m) mx = maxOf(mx, nums[i][j])
            ans += mx
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def matrixSum(self, nums: list[list[int]]) -> int:
        for row in nums:
            row.sort()
        ans = 0
        for j in range(len(nums[0])-1, -1, -1):
            mx = 0
            for i in range(len(nums)):
                mx = max(mx, nums[i][j])
            ans += mx
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn matrix_sum(nums: Vec<Vec<i32>>) -> i32 {
        let m = nums.len();
        let n = nums[0].len();
        let mut nums = nums;
        for row in &mut nums {
            row.sort();
        }
        let mut ans = 0;
        for j in (0..n).rev() {
            let mut mx = 0;
            for i in 0..m {
                mx = mx.max(nums[i][j]);
            }
            ans += mx;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    matrixSum(nums: number[][]): number {
        for (const row of nums) row.sort((a, b) => a - b);
        let ans = 0;
        const m = nums.length, n = nums[0].length;
        for (let j = n-1; j >= 0; j--) {
            let mx = 0;
            for (let i = 0; i < m; i++) mx = Math.max(mx, nums[i][j]);
            ans += mx;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n log n) — Each row is sorted, and then each column is processed in O(m) time.
  • 🧺 Space complexity: O(1) — Sorting is in-place, and only a few variables are used.