Delete Greatest Value in Each Row — Problem & Solution
Delete Greatest Value in Each Row solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Delete Greatest Value in Each Row is an easy coding problem on arrays, sorting and matrix, asked in Amazon, Google and Accenture interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Matrix, Simulation
- Asked at: Amazon, Google, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Repeat until the grid is empty:
- delete the greatest value from each row (on a tie within a row, delete any one of them);
- add the largest of the deleted values to your answer.
Return the final answer.
Example 1
Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: Rounds delete `{4,3}`, `{2,3}` and `{1,1}`, adding 4 + 3 + 1.
Example 2
Input: grid = [[10]]
Output: 10
Example 3
Input: grid = [[1,2],[3,4]]
Output: 7
Explanation: Delete `{2,4}` for 4, then `{1,3}` for 3.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 100
Hints for Delete Greatest Value in Each Row
Hint 1
In round
k, each row gives up itsk-th largest value.Hint 2
So sorting every row turns the simulation into a column scan.
Hint 3
Sum the column maxima of the sorted grid.
How to solve Delete Greatest Value in Each Row
Sort every row. Round k then deletes exactly the k-th largest of each row — that is, one column of the sorted grid — so the answer is the sum of the column maxima.
Approach
- Sort each row ascending.
- For each column, take the maximum down the column.
- Sum those maxima.
Why it works
Sorting is what removes the simulation: rounds proceed in lockstep and a row always yields its next-largest remaining value, so which values meet in a round is fixed in advance by rank. Direction does not matter — summing column maxima of the ascending sort visits the same multiset of rounds as descending, just in the other order.
Complexity
- Time —
O(m · n log n) - Space —
O(m · n)
Pitfalls
- Each row loses one value per round, not just the global maximum.
- Ties inside a row are irrelevant — the values are equal.
- The answer accumulates one value per round, which is
nin total.
Reference solution
Python
from typing import List
def deleteGreatestValue(grid: List[List[int]]) -> int:
rows = [sorted(r) for r in grid]
return sum(max(col) for col in zip(*rows))Java
public static int deleteGreatestValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] rows = new int[m][];
for (int i = 0; i < m; i++) {
rows[i] = grid[i].clone();
Arrays.sort(rows[i]);
}
int total = 0;
for (int col = 0; col < n; col++) {
int best = 0;
for (int i = 0; i < m; i++) best = Math.max(best, rows[i][col]);
total += best;
}
return total;
}C++
int deleteGreatestValue(vector<vector<int>>& grid) {
vector<vector<int>> rows = grid;
for (auto& r : rows) sort(r.begin(), r.end());
int m = (int) rows.size(), n = (int) rows[0].size();
int total = 0;
for (int col = 0; col < n; col++) {
int best = 0;
for (int i = 0; i < m; i++) best = max(best, rows[i][col]);
total += best;
}
return total;
}JavaScript
var deleteGreatestValue = function(grid) {
var rows = [];
for (var i = 0; i < grid.length; i++) {
var r = grid[i].slice();
r.sort(function(a, b) { return a - b; });
rows.push(r);
}
var m = rows.length, n = rows[0].length, total = 0;
for (var col = 0; col < n; col++) {
var best = 0;
for (i = 0; i < m; i++) if (rows[i][col] > best) best = rows[i][col];
total += best;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms