Delete Greatest Value in Each Row - Solution & Explanation
Problem Statement
You are given an m x n matrix grid consisting of positive integers.
Perform the following operation until grid becomes empty:
- Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
- Add the maximum of deleted elements to the answer.
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] <= 100
Approach Overview
Problem 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 1: Greedy Approach
The greedy approach involves making a series of choices over time, each of which simply looks the best at the moment. In this method, we select the local optimal solution at each point with the hope of finding a global optimum. For instance, if we need to choose the smallest or largest element to optimize a result, this approach makes the choice at each step.
This solution sorts intervals based on their start times to process them in order. It uses a greedy technique to extend the current interval when possible or start a new one otherwise, ensuring that we cover as much ground as possible.
Complexity
Time Complexity: O(n log n) due to sorting, where n is the number of intervals.
Space Complexity: O(1) as we use a constant amount of extra space.
Approach 2: Dynamic Programming Approach
Dynamic Programming (DP) is an optimization approach where the overall problem is broken down into simpler sub-problems. These sub-problems are solved just once and stored for future use. This technique is suitable for optimizing overlapping sub-problems and solving them efficiently.
This solution leverages dynamic programming to find the optimal set of non-overlapping intervals that maximizes the covered length. By maintaining a DP table that records the best option for each interval considered, it builds the solution using optimal substructure.
Code
C++
JavaScript
Complexity
Time Complexity: O(n^2) due to the nested loop checking for intervals.
Space Complexity: O(n) for the DP table.
Approach 3: 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.
Next, we traverse each column, take the maximum value from each column, and add it to the answer.
The time complexity is O(m times n times log n), and the space complexity is O(log n). Here, m and n are the number of rows and columns of the matrix, respectively.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n log n) due to sorting, where n is the number of intervals. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to the nested loop checking for intervals. |
| Sorting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2500. Delete Greatest Value in Each Row | Weekly Contest 323 | LeetCode 2500 • Bro Coders • 2,275 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Delete Greatest Value in Each Row easy or hard?
Delete Greatest Value in Each Row Python/Java solution
How to solve Delete Greatest Value in Each Row in O(n)?
What is the best approach for Delete Greatest Value in Each Row?
Is Delete Greatest Value in Each Row asked at Google/Amazon/Meta?
What data structure is used in Delete Greatest Value in Each Row?
What is the time complexity of Delete Greatest Value in Each Row?
Ready to solve this problem?
Practice Delete Greatest Value in Each Row with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor