LeetCode 2500 - Delete Greatest Value in Each Row

The problem presents an m x n matrix grid of positive integers and asks us to simulate a repeated deletion process on it. In each operation, for every row in the matrix, we remove the greatest element.

leetcodeeasyarraysortingheap-(priority-queue)matrixsimulation

LeetCode Problem 2500

Difficulty: 🟢 Easy
Topics: Array, Sorting, Heap (Priority Queue), Matrix, Simulation

Solution

Problem Understanding

The problem presents an m x n matrix grid of positive integers and asks us to simulate a repeated deletion process on it. In each operation, for every row in the matrix, we remove the greatest element. After deleting these elements, we take the largest of the removed elements from all rows and add it to a running total, which will be the final answer. This process continues until all columns are removed, i.e., the matrix becomes empty.

The input represents a rectangular grid of integers. Each row may contain duplicate values, but only one occurrence of the maximum value per row is removed per operation. The expected output is a single integer representing the sum of the maximum values from each deletion step.

The constraints are moderate: 1 <= m, n <= 50 and 1 <= grid[i][j] <= 100, meaning the input size is small enough that even relatively straightforward solutions can work efficiently. Important edge cases include matrices with a single row or column, all elements equal, or minimal matrix sizes (1x1), which should all be handled correctly by the algorithm.

Approaches

Brute Force

The brute-force approach directly simulates the problem statement. For each operation, we iterate through each row, find the maximum element, remove it, and then compute the maximum among these removed elements to add to the total sum. While correct, this approach involves repeated scans of each row for every deletion, leading to a time complexity of roughly O(m * n^2) because each of the n deletion steps requires scanning m rows that may each contain up to n elements. This works within the constraints, but it is not optimal.

Optimal Approach

The key insight for optimization is that the maximum of a row always comes from the largest remaining elements in sorted order. If we sort each row in ascending order at the start, we can simply delete the last element of each row for each operation without scanning the row repeatedly. The largest element among all last elements of rows can be computed in O(m) time per operation. This reduces the effective time complexity to O(m * n log n) due to the initial row sorting, which is efficient for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n^2) O(1) Directly simulates deletions by scanning each row repeatedly
Optimal O(m * n log n) O(1) Sort rows once, then remove last element per row in each operation

Algorithm Walkthrough

  1. Initialize a variable answer to 0 to keep track of the cumulative sum of the maximum deleted elements.

  2. Sort each row of the grid in ascending order. This ensures the greatest element of each row is at the end.

  3. Repeat for n steps, where n is the number of columns in the grid:

  4. Initialize a variable current_max to 0 for this operation.

  5. For each row, remove the last element (which is the largest due to sorting) and update current_max if this element is greater than current_max.

  6. Add current_max to answer.

  7. Return answer.

Why it works: Sorting each row ensures that deletions always target the largest element without scanning the row repeatedly. The invariant is that at each operation, we correctly remove the row maxima and compute the overall maximum among them, matching the problem description.

Python Solution

from typing import List

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        answer = 0
        
        # Sort each row so that the largest element is at the end
        for row in grid:
            row.sort()
        
        n = len(grid[0])
        
        # Perform n operations, each removing the largest element from each row
        for _ in range(n):
            current_max = 0
            for row in grid:
                val = row.pop()  # Remove largest element
                current_max = max(current_max, val)
            answer += current_max
        
        return answer

In this Python implementation, we first sort each row so that the largest element is at the end. Then, for each of the n operations, we pop the last element from every row and track the maximum of these popped values. This maximum is added to answer. This approach avoids scanning rows repeatedly for maximum values, making it efficient and simple.

Go Solution

func deleteGreatestValue(grid [][]int) int {
    answer := 0
    m := len(grid)
    n := len(grid[0])
    
    // Sort each row
    for i := 0; i < m; i++ {
        row := grid[i]
        for j := 0; j < len(row)-1; j++ {
            for k := 0; k < len(row)-j-1; k++ {
                if row[k] > row[k+1] {
                    row[k], row[k+1] = row[k+1], row[k]
                }
            }
        }
    }
    
    // Perform n operations
    for op := 0; op < n; op++ {
        currentMax := 0
        for i := 0; i < m; i++ {
            row := grid[i]
            val := row[len(row)-1]
            grid[i] = row[:len(row)-1]
            if val > currentMax {
                currentMax = val
            }
        }
        answer += currentMax
    }
    
    return answer
}

The Go implementation mirrors the Python logic. Each row is sorted using a nested loop for clarity (Go standard library sorting could also be used). During each operation, the last element of each row is removed, and the maximum among these removed elements is accumulated into answer.

Worked Examples

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

Operation Row Deletions Max of Deletions Answer
1 [4, 3] 4 4
2 [2, 3] 3 7
3 [1, 1] 1 8

Example 2: grid = [[10]]

Operation Row Deletions Max of Deletions Answer
1 [10] 10 10

Complexity Analysis

Measure Complexity Explanation
Time O(m * n log n) Sorting each of the m rows takes O(n log n), and popping n elements per row is O(n)
Space O(1) Modifies the grid in-place, only constant extra space for counters

The complexity is dominated by sorting the rows initially. Each deletion step is linear in m since we only pop the last element from each row.

Test Cases

# Provided examples
assert Solution().deleteGreatestValue([[1,2,4],[3,3,1]]) == 8  # multiple rows
assert Solution().deleteGreatestValue([[10]]) == 10           # single element

# Edge cases
assert Solution().deleteGreatestValue([[5,5,5],[5,5,5]]) == 15  # all equal elements
assert Solution().deleteGreatestValue([[1]]) == 1              # 1x1 matrix
assert Solution().deleteGreatestValue([[1,2,3]]) == 3          # single row
assert Solution().deleteGreatestValue([[1],[2],[3]]) == 6      # single column
assert Solution().deleteGreatestValue([[1,2],[3,4]]) == 6      # 2x2 matrix
Test Why
[[1,2,4],[3,3,1]] Tests multiple rows with different maximum values
[[10]] Tests the smallest possible matrix
[[5,5,5],[5,5,5]] Tests identical elements to ensure maxima handling
[[1]] Edge case 1x1
[[1,2,3]] Single row matrix
[[1],[2],[3]] Single column matrix
[[1,2],[3,4]] Small 2x2 matrix

Edge Cases

  1. Single Row or Column: For a matrix with only one row or one column, the algorithm must correctly compute the maximum deletions without errors due to empty rows. Sorting ensures the largest element is at the end, so the pop operation always works.
  2. All Elements Equal: When all elements are the same, the maximum of deletions is the same for each operation. This can be a source of confusion if the implementation incorrectly tries to remove multiple instances per row. The algorithm handles this by removing one element per row per operation.
  3. Minimal Matrix (1x1): The smallest possible input could be a 1x1 matrix. The algorithm correctly handles this by popping the single element and adding it to the answer, then terminating as the matrix becomes empty.