#2500

Easy

LeetCode Problem Workspace

Delete Greatest Value in Each Row

Calculate the total of removed maximum values from each row of a matrix, iterating until all columns are deleted efficiently.

array sorting heap priority queue matrix simulation

Problem Statement

You are given an m x n matrix grid filled with positive integers. In each step, select the largest remaining value from each row and remove it from the matrix. Continue removing the greatest values until all columns are empty, summing all removed numbers.

After each removal, the number of columns decreases by one. Return the total sum of all values removed during this process. Each selection in a row should always pick the current maximum, reflecting the array plus sorting pattern.

Examples

Example 1

Input: grid = [[1,2,4],[3,3,1]]

Output: 8

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

Input: grid = [[10]]

Output: 10

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 Approach

Sort Rows for Easy Maximum Selection

Sort each row of the matrix in descending order so the largest unremoved element is always at a known index. This avoids scanning each row for the maximum in every iteration.

Iterative Column Removal

Iterate column by column: for each column index, remove the element at that position from every row and accumulate the sum. This directly simulates the process while preserving array order.

Use Priority Structures if Needed

For larger matrices or variable row lengths, a heap or priority queue per row can track maximums efficiently. Pop the largest from each row in each iteration and sum the values until all elements are removed.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n log n) for sorting all rows and O(m * n) for iterative removal, resulting in O(m * n log n). Space complexity is O(1) extra if sorting in place, or O(m * n) if storing sorted copies.

What Interviewers Usually Probe

Watch for off-by-one errors when columns shrink after each removal.
Check if sorting each row up front reduces repeated maximum searches.
Be aware that multiple identical maximums in a row can be removed in any order, the sum remains correct.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the number of columns decreases each iteration leads to index errors.
Not sorting rows first can result in inefficient repeated maximum searches.
Adding all removed elements instead of only the current maximum per row will give wrong total.

Follow-up variants

Calculate sum of minimum values removed from each row instead of maximums.
Apply the same operation but only on specific columns based on a condition.
Handle rectangular matrices where rows have different lengths after removals.

FAQ

What is the main pattern used in Delete Greatest Value in Each Row?

The problem primarily uses the array plus sorting pattern, where each row is sorted to efficiently pick maximums.

How do I handle multiple identical maximums in a row?

You can remove any one of the identical maximums, as the total sum remains the same, the key is to select a maximum per iteration.

What is the time complexity for this problem?

Sorting each row gives O(m * n log n), and iterating through all columns adds O(m * n), so overall time complexity is O(m * n log n).

Can I use a heap to solve this problem?

Yes, using a heap per row lets you efficiently track and remove the largest element in each iteration, which is helpful for larger matrices.

What common mistakes should I avoid?

Avoid forgetting column reduction after each iteration, not sorting rows upfront, and accidentally summing all row elements instead of only the maximums.

terminal

Solution

Solution 1: Sorting

Since each operation involves removing the maximum value from each row and then adding the maximum value to the answer, we can first sort each row.

1

2

3

4

5

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        for row in grid:
            row.sort()
        return sum(max(col) for col in zip(*grid))

Continue Practicing

#2679 sum in a matrix #2503 maximum number of points from grid queries #2593 find score of an array after marking all elements