Delete Greatest Value in Each Row

Problem

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
Add the maximum of deleted elements to the answer.

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10



![](https://assets.leetcode.com/uploads/2022/10/19/q1ex1.jpg)

Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
The final answer = 4 + 3 + 1 = 8.

Example 2

1
2
3
4
5
6
7
8



![](https://assets.leetcode.com/uploads/2022/10/19/q1ex2.jpg)

Input: grid = [[10]]
Output: 10
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
The final answer = 10.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 100

Solution

Method 1 – Column-wise Maximums After Row Sorting

Intuition

If we sort each row in non-increasing order, then in each operation, the greatest value in each row will always be at the front. For each column (from left to right), the maximum value among all rows in that column is the value added to the answer for that operation.

Approach

For each row, sort it in descending order.
For each column index, find the maximum value among all rows at that column.
Sum up these maximums for all columns to get the answer.

Code

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


class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for (auto& row : grid) sort(row.rbegin(), row.rend());
        for (int j = 0; j < n; ++j) {
            int mx = 0;
            for (int i = 0; i < m; ++i) mx = max(mx, grid[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 deleteGreatestValue(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for i := 0; i < m; i++ {
        sort.Sort(sort.Reverse(sort.IntSlice(grid[i])))
    }
    ans := 0
    for j := 0; j < n; j++ {
        mx := 0
        for i := 0; i < m; i++ {
            if grid[i][j] > mx {
                mx = grid[i][j]
            }
        }
        ans += mx
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        for (int[] row : grid) {
            java.util.Arrays.sort(row);
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int tmp = row[l]; row[l] = row[r]; row[r] = tmp;
            }
        }
        for (int j = 0; j < n; j++) {
            int mx = 0;
            for (int i = 0; i < m; i++) mx = Math.max(mx, grid[i][j]);
            ans += mx;
        }
        return ans;
    }
}

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


class Solution {
    fun deleteGreatestValue(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        for (row in grid) row.sortDescending()
        var ans = 0
        for (j in 0 until n) {
            var mx = 0
            for (i in 0 until m) mx = maxOf(mx, grid[i][j])
            ans += mx
        }
        return ans
    }
}

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


class Solution:
    def deleteGreatestValue(self, grid: list[list[int]]) -> int:
        m: int = len(grid)
        n: int = len(grid[0])
        for row in grid:
            row.sort(reverse=True)
        ans: int = 0
        for j in range(n):
            mx = 0
            for i in range(m):
                mx = max(mx, grid[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 delete_greatest_value(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut grid = grid;
        for row in &mut grid {
            row.sort_by(|a, b| b.cmp(a));
        }
        let mut ans = 0;
        for j in 0..n {
            let mut mx = 0;
            for i in 0..m {
                mx = mx.max(grid[i][j]);
            }
            ans += mx;
        }
        ans
    }
}

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


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

Complexity

⏰ Time complexity: O(m * n * log n), where m is the number of rows and n is the number of columns, due to sorting each row.
🧺 Space complexity: O(1), ignoring input and output, as sorting is in-place.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Column-wise Maximums After Row Sorting#

Intuition#

Approach#

Code#

Complexity#