Problem Description

You have a matrix grid with m rows and n columns filled with positive integers. You need to perform a series of operations on this matrix until it becomes empty.

In each operation:

1. Find and delete the largest value from each row (if there are multiple elements with the same maximum value in a row, you can delete any one of them)
2. Among all the deleted elements from this operation, find the maximum value and add it to your running answer

After each operation, the matrix will have one fewer column since you're removing one element from each row.

For example, if you have a 3×3 matrix:

• In the first operation, you delete the maximum from each of the 3 rows, then add the largest of these 3 deleted values to your answer
• In the second operation, you work with a 3×2 matrix (one column removed), again delete the maximum from each row, and add the largest deleted value to your answer
• Continue until the matrix is empty

The solution approach sorts each row first. After sorting, the largest values in each row are aligned in the rightmost column, the second-largest values in the second-rightmost column, and so on. Then, by taking the maximum value from each column (using zip(*grid) to transpose the matrix), we get the maximum deleted value for each operation. The sum of these maximum values gives us the final answer.

Intuition

The key insight is recognizing that we need to repeatedly find the maximum element from each row and then take the maximum among those deleted elements. Since we're going to delete elements column by column (one element from each row per operation), we need a way to organize the data to make this process efficient.

Think about what happens if we sort each row individually. After sorting, the largest element in each row will be at the rightmost position, the second-largest at the second-rightmost position, and so on. This arrangement perfectly aligns with our deletion pattern - we delete from largest to smallest in each row.

Once all rows are sorted, we can visualize the matrix differently. The last column now contains the largest element from each row (these will be deleted in the first operation). The second-to-last column contains the second-largest element from each row (deleted in the second operation), and so on.

To find the answer, we need the maximum value among elements deleted in each operation. Since elements deleted in the same operation are now in the same column after sorting, we can simply find the maximum value in each column and sum them up.

For example, if we have:

Original: [[5,1,3], [2,9,6]]
After [sorting](/problems/sorting_summary): [[1,3,5], [2,6,9]]

Column-wise maximums: max(1,2)=2, max(3,6)=6, max(5,9)=9 Answer: 2 + 6 + 9 = 17

This transformation from a row-wise deletion problem to a column-wise maximum problem after sorting is the core insight that makes the solution elegant and efficient.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a two-step approach that transforms the problem into a simpler one:

Step 1: Sort Each Row

for row in grid:
    row.sort()

We iterate through each row in the grid and sort it in ascending order. This in-place sorting operation ensures that:

• The smallest elements are positioned at the beginning of each row
• The largest elements are positioned at the end of each row
• Elements that will be deleted in the same operation are now aligned in the same column

Step 2: Calculate Column-wise Maximums and Sum

return sum(max(col) for col in zip(*grid))

This line performs multiple operations:

1. zip(*grid) - The asterisk operator unpacks the grid rows and zip transposes the matrix. This groups elements by column instead of by row. For example:

   • If grid = [[1,3,5], [2,6,9]]
   • zip(*grid) produces [(1,2), (3,6), (5,9)]

2. max(col) for col in zip(*grid) - For each column (which represents elements deleted in the same operation), we find the maximum value. This gives us the maximum deleted element for each operation.

3. sum(...) - Finally, we sum all these maximum values to get our answer.

The beauty of this approach is that it avoids simulating the actual deletion process. Instead of repeatedly finding and removing maximum elements, we reorganize the data once through sorting and then simply traverse the columns to compute the result. The time complexity is O(m * n * log(n)) for sorting m rows of n elements each, plus O(m * n) for the final traversal.

Example Walkthrough

Let's walk through a concrete example with a 3×3 matrix to illustrate the solution approach.

Initial Grid:

grid = [[7, 2, 1],
        [6, 4, 2],
        [6, 5, 3]]

Step 1: Sort Each Row

We sort each row independently in ascending order:

grid = [[1, 2, 7],  // sorted from [7, 2, 1]
        [2, 4, 6],  // sorted from [6, 4, 2]
        [3, 5, 6]]  // sorted from [6, 5, 3]

After sorting, notice how the elements are organized:

• Column 0: [1, 2, 3] - smallest elements from each row
• Column 1: [2, 4, 5] - middle elements from each row
• Column 2: [7, 6, 6] - largest elements from each row

Step 2: Find Column-wise Maximums

Using zip(*grid) to transpose and get columns:

• Column 0: (1, 2, 3) → max = 3
• Column 1: (2, 4, 5) → max = 5
• Column 2: (7, 6, 6) → max = 7

These maximums represent:

• Operation 1: We delete 7, 6, 6 from original rows → max deleted = 7
• Operation 2: We delete 2, 4, 5 from remaining elements → max deleted = 5
• Operation 3: We delete 1, 2, 3 from remaining elements → max deleted = 3

Final Answer: Sum of maximums = 7 + 5 + 3 = 15

The key insight is that sorting aligns elements by their deletion order - the rightmost column contains elements deleted first (largest from each row), the next column contains elements deleted second, and so on. This transforms the row-wise deletion problem into a simple column-wise maximum calculation.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × log n)

The time complexity breaks down as follows:

• The outer loop iterates through each row in the grid, which takes O(m) iterations where m is the number of rows
• For each row, row.sort() is called, which has a time complexity of O(n log n) where n is the number of columns (length of each row)
• The zip(*grid) operation transposes the matrix in O(m × n) time
• The sum(max(col) for col in zip(*grid)) iterates through n columns and finds the maximum of m elements in each column, taking O(m × n) time

The dominant operation is sorting each row, so the overall time complexity is O(m × n × log n).

Space Complexity: O(log n)

The space complexity analysis:

• The sorting operation uses O(log n) space for the recursive call stack in Python's Timsort algorithm
• The zip(*grid) creates an iterator that doesn't consume additional space proportional to the input
• The generator expression max(col) for col in zip(*grid) processes one column at a time without storing all results
• No additional data structures are created that scale with input size

Therefore, the space complexity is O(log n), dominated by the sorting algorithm's space requirements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Deletion Order

The Issue: A common misconception is thinking that we need to delete the globally largest element from the entire matrix in each operation. This leads to incorrect solutions where developers try to find the maximum across all rows first, then remove it.

What Actually Happens: We delete the largest element from each row independently in every operation, then only consider the maximum among those deleted elements for our answer.

Incorrect Approach Example:

# WRONG: Trying to find global maximum first
def deleteGreatestValue(self, grid):
    result = 0
    while grid and grid[0]:
        max_val = max(max(row) for row in grid)
        result += max_val
        # Remove max_val from wherever it appears... (incorrect logic)
    return result

Correct Understanding: The sorting approach works because it aligns elements by their relative rank within each row. After sorting, the rightmost column contains each row's maximum, ensuring we're deleting the correct elements.

Pitfall 2: Attempting In-Place Deletion Simulation

The Issue: Trying to simulate the actual deletion process by removing elements from the matrix after each operation, which leads to complex index management and potential errors.

Problems with This Approach:

• Removing elements from lists is O(n) operation
• Managing changing indices becomes error-prone
• Overall complexity increases unnecessarily

Inefficient Simulation Example:

# INEFFICIENT: Actually deleting elements
def deleteGreatestValue(self, grid):
    result = 0
    while grid[0]:  # While columns remain
        deleted_values = []
        for row in grid:
            max_val = max(row)
            max_idx = row.index(max_val)
            deleted_values.append(max_val)
            row.pop(max_idx)  # O(n) deletion
        result += max(deleted_values)
    return result

Better Solution: The sorting approach avoids actual deletion by pre-organizing the data, making the problem a simple column-wise maximum calculation.

Pitfall 3: Confusion with zip(*grid) Transposition

The Issue: Not understanding how zip(*grid) works or forgetting the unpacking operator *, leading to incorrect column extraction.

Common Mistakes:

# WRONG: Missing unpacking operator
return sum(max(col) for col in zip(grid))  # This zips rows, not columns

# WRONG: Trying to manually transpose
columns = []
for j in range(len(grid[0])):
    col = []
    for i in range(len(grid)):
        col.append(grid[i][j])
    columns.append(col)
# This works but is unnecessarily verbose

Correct Usage: The * operator unpacks the grid so that each row becomes a separate argument to zip(), which then pairs up elements by position, effectively transposing the matrix.

Pitfall 4: Not Sorting In-Place

The Issue: Creating new sorted arrays instead of sorting in-place, which uses extra space unnecessarily.

Space-Inefficient Approach:

def deleteGreatestValue(self, grid):
    sorted_grid = []
    for row in grid:
        sorted_grid.append(sorted(row))  # Creates new list
    return sum(max(col) for col in zip(*sorted_grid))

Optimal Approach:

def deleteGreatestValue(self, grid):
    for row in grid:
        row.sort()  # Sorts in-place, O(1) extra space
    return sum(max(col) for col in zip(*grid))

The in-place sorting maintains O(1) additional space complexity (excluding the space needed for sorting), while the alternative creates an entirely new grid with O(m*n) extra space.