Watch 10 video solutions for Delete Greatest Value in Each Row, a easy level problem involving Array, Sorting, Heap (Priority Queue). This walkthrough by Bro Coders has 2,249 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n matrix grid consisting of positive integers.
Perform the following operation until grid becomes empty:
Note that the number of columns decreases by one after each operation.
Return the answer after performing the operations described above.
Example 1:
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:
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.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 100Problem Overview: You are given an matrix of integers. In each step, remove the largest element from every row, then add the maximum among those removed values to the answer. Repeat until the grid becomes empty. The challenge is organizing these removals efficiently while tracking the maximum picked in every round.
Approach 1: Greedy Row Sorting (O(m * n log n) time, O(1) extra space)
The key observation: the largest elements removed from each row form "rounds" when rows are sorted. Sort every row in ascending order using sorting. After sorting, the last column holds each row's largest value, the second‑last column holds the second largest, and so on. Iterate columns from right to left. For each column index, scan all rows and take the maximum value among them, then add it to the total. Sorting aligns removals across rows so each column naturally represents one deletion round.
This greedy strategy works because the deletion order inside a row does not affect other rows. Once rows are sorted, the problem reduces to repeatedly selecting the largest value among the current "top" elements of each row.
Approach 2: Heap Simulation (O(m * n log n) time, O(m * n) space)
Another direct simulation uses a max heap for every row with a heap (priority queue). Push all row elements into a max heap. During each round, pop the largest value from every heap and track the maximum among those popped numbers. Add that maximum to the answer. Continue until heaps become empty.
This approach mirrors the problem statement exactly: repeatedly remove row maximums and evaluate the global maximum. However, heap maintenance adds extra memory and logarithmic operations, making it slightly heavier than sorting once.
Approach 3: Column Aggregation (Dynamic Programming View) (O(m * n log n) time, O(n) space)
After sorting each row, you can treat each column as an independent stage of the process. Maintain an array where index j represents the best value obtainable when removing the j-th largest elements. For each column, compute the maximum across rows and accumulate it into the result. This resembles a simple dynamic programming accumulation because each column's contribution builds the final answer step by step.
The DP interpretation doesn't change complexity but clarifies that once rows are sorted, the remaining work is just scanning columns and aggregating the optimal value per stage.
Recommended for interviews: The greedy sorting approach is what interviewers expect. Sorting rows once simplifies the entire simulation and leads to clean O(m * n log n) time with constant extra space. The heap solution shows you understand priority queues, but the greedy alignment insight demonstrates stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Row Sorting | O(m * n log n) | O(1) extra | Best general solution; simple implementation after sorting each row |
| Heap Simulation | O(m * n log n) | O(m * n) | Useful when rows arrive dynamically or you want to simulate deletions directly |
| Column Aggregation (DP View) | O(m * n log n) | O(n) | Helpful for reasoning about column stages after sorting rows |