Delete Greatest Value in Each Row

Easy
1074.

Delete Greatest Value in Each Row

Delete Greatest Value in Each Row is an easy coding problem on arrays, sorting and matrix, asked in Amazon, Google and Accenture interviews.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var deleteGreatestValue = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 100

Hints for Delete Greatest Value in Each Row

  1. Hint 1

    In round k, each row gives up its k-th largest value.

  2. Hint 2

    So sorting every row turns the simulation into a column scan.

  3. 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

  1. Sort each row ascending.
  2. For each column, take the maximum down the column.
  3. 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 n in 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