2500. Delete Greatest Value in Each Row LeetCode Solution
In this guide, you will get 2500. Delete Greatest Value in Each Row LeetCode Solution with the best time and space complexity. The solution to Delete Greatest Value in Each Row problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Delete Greatest Value in Each Row
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.
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.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 100
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(\texttt{sort})
2500. Delete Greatest Value in Each Row LeetCode Solution in C++
class Solution {
public:
int deleteGreatestValue(vector<vector<int>>& grid) {
int ans = 0;
for (vector<int>& row : grid)
ranges::sort(row);
for (int j = 0; j < grid[0].size(); ++j) {
int maxOfColumn = 0;
for (int i = 0; i < grid.size(); ++i)
maxOfColumn = max(maxOfColumn, grid[i][j]);
ans += maxOfColumn;
}
return ans;
}
}; /* code provided by PROGIEZ */
2500. Delete Greatest Value in Each Row LeetCode Solution in Java
class Solution {
public int deleteGreatestValue(int[][] grid) {
int ans = 0;
for (int[] row : grid)
Arrays.sort(row);
for (int j = 0; j < grid[0].length; ++j) {
int maxOfColumn = 0;
for (int i = 0; i < grid.length; ++i)
maxOfColumn = Math.max(maxOfColumn, grid[i][j]);
ans += maxOfColumn;
}
return ans;
}
} // code provided by PROGIEZ
2500. Delete Greatest Value in Each Row LeetCode Solution in Python
class Solution:
def deleteGreatestValue(self, grid: list[list[int]]) -> int:
for row in grid:
row.sort()
return sum(max(col) for col in zip(*grid)) # code by PROGIEZ
