Difficulty: Easy | Acceptance: 79.90% | Paid: No Topics: Array, Sorting, Heap (Priority Queue), Matrix, Simulation
You are given an m x n matrix grid consisting of positive integers.
Perform the following operation until grid becomes empty:
- In each operation, delete the element with the greatest value from each row. If multiple elements have the greatest value, delete any of them.
- Add the maximum of deleted elements to the answer.
Return the answer after performing the operations described above.
- Examples
- Constraints
- Sorting Approach
- Priority Queue Approach
- Simulation Approach
Examples
Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation:
- In the first operation, we delete 4 from the first row and 3 from the second row (the greatest values in the rows). The maximum of deleted elements is max(4,3) = 4.
- In the second operation, we delete 2 from the first row and 3 from the second row. The maximum of deleted elements is max(2,3) = 3.
- In the third operation, we delete 1 from the first row and 1 from the second row. The maximum of deleted elements is max(1,1) = 1.
- The answer is 4 + 3 + 1 = 8.
Input: grid = [[10]]
Output: 10
Explanation:
- In the first operation, we delete 10 from the first row. The maximum of deleted elements is max(10) = 10.
- The answer is 10.
Constraints
m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10³
Sorting Approach
Intuition Sort each row in descending order, then for each column position, the k-th operation will pick the k-th element from each row, so we just need to find the column maximums.
Steps
- Sort each row in descending order
- For each column, find the maximum value across all rows
- Sum all these column maximums
python
class Solution:
def deleteGreatestValue(self, grid: List[List[int]]) -> int:
for row in grid:
row.sort(reverse=True)
ans = 0
for j in range(len(grid[0])):
max_val = 0
for i in range(len(grid)):
max_val = max(max_val, grid[i][j])
ans += max_val
return ansComplexity
- Time: O(m × n × log n) for sorting each row
- Space: O(1) if sorting in-place, O(m × n) otherwise
- Notes: Most efficient approach, leverages the fact that sorting aligns elements by their deletion order
Priority Queue Approach
Intuition Use a max heap for each row to efficiently extract the maximum element in each operation, simulating the process directly.
Steps
- Create a max heap for each row
- In each operation, pop the maximum from each heap
- Add the maximum of these popped values to the answer
- Continue until all heaps are empty
python
import heapq
class Solution:
def deleteGreatestValue(self, grid: List[List[int]]) -> int:
heaps = []
for row in grid:
heap = [-x for x in row]
heapq.heapify(heap)
heaps.append(heap)
ans = 0
while heaps[0]:
max_val = float('-inf')
for heap in heaps:
max_val = max(max_val, -heapq.heappop(heap))
ans += max_val
return ansComplexity
- Time: O(m × n × log n) for heap operations
- Space: O(m × n) for storing heaps
- Notes: Directly simulates the process, useful when you need to process elements in order without full sorting
Simulation Approach
Intuition Directly simulate the process by finding and removing the maximum element from each row in each operation.
Steps
- While grid is not empty, for each row find the maximum element
- Track the maximum across all rows in this operation
- Remove the maximum element from each row
- Add the tracked maximum to the answer
python
class Solution:
def deleteGreatestValue(self, grid: List[List[int]]) -> int:
ans = 0
while grid[0]:
max_in_round = 0
for i in range(len(grid)):
max_idx = 0
for j in range(1, len(grid[i])):
if grid[i][j] > grid[i][max_idx]:
max_idx = j
max_in_round = max(max_in_round, grid[i][max_idx])
grid[i].pop(max_idx)
ans += max_in_round
return ansComplexity
- Time: O(m × n²) for finding max in each row and shifting elements
- Space: O(1) additional space
- Notes: Least efficient but most intuitive approach, good for understanding the problem