# Delete Greatest Value in Each Row
**Difficulty:** EASY
[External](https://leetcode.com/problems/delete-greatest-value-in-each-row)
Canonical: https://scaleengineer.com/dsa/problems/delete-greatest-value-in-each-row
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/delete-greatest-value-in-each-row/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/delete-greatest-value-in-each-row/image1.jpg) 

**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`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. In each step, it iterates through every row to find the maximum element, adds it to a temporary list, and then removes it. After processing all rows, it finds the maximum among the removed elements and adds it to the total answer. This process is repeated until the grid becomes empty.
**Time:** O(m * n^2). The main loop runs `n` times. Inside, we iterate through `m` rows. For each row, finding the max takes O(k) and removing from an `ArrayList` takes O(k), where `k` is the current number of elements in the row (from `n` down to 1). The total work for the inner loops is a sum of an arithmetic series, resulting in `m * O(n^2)`. · **Space:** O(m * n). We create a `List<List<Integer>>` to store a copy of the grid, which requires space proportional to the size of the grid.
**Pros:** Conceptually straightforward as it directly follows the problem's description.
**Cons:** Highly inefficient due to repeated linear scans to find the maximum element in each row.; The `remove` operation on an `ArrayList` is slow (O(k) where k is the number of elements), contributing to the poor time complexity.; Requires O(m*n) auxiliary space to create a mutable copy of the grid.
### Explanation
To faithfully simulate the operation, we first need a data structure that allows for efficient removal of elements. A standard 2D array is not suitable, so we convert the input `int[][]` grid into a `List<List<Integer>>`. The simulation then proceeds for `n` steps, where `n` is the original number of columns.

In each step:
1. We prepare to find the maximum of the elements that will be deleted in this step.
2. We iterate through each row of our list-based grid.
3. For each row, we perform a linear scan to find the greatest value and its index.
4. This greatest value is a candidate for the value to be added to our total answer in this step.
5. We then remove this element from the row. This is a costly operation as it may require shifting subsequent elements.
6. After processing all rows, we will have found the maximum among all the deleted elements for this step.
7. This maximum is added to our final result.

This entire process is repeated `n` times.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;

        // Convert to List of Lists for easier removal
        List<List<Integer>> gridList = new ArrayList<>();
        for (int[] row : grid) {
            List<Integer> newRow = new ArrayList<>();
            for (int val : row) {
                newRow.add(val);
            }
            gridList.add(newRow);
        }

        int result = 0;
        for (int k = 0; k < n; k++) {
            int maxOfDeleted = 0;
            for (int i = 0; i < m; i++) {
                List<Integer> currentRow = gridList.get(i);
                int maxVal = -1;
                int maxIdx = -1;
                // Find the max in the current row
                for (int j = 0; j < currentRow.size(); j++) {
                    if (currentRow.get(j) > maxVal) {
                        maxVal = currentRow.get(j);
                        maxIdx = j;
                    }
                }
                // "Delete" the max value
                if (maxIdx != -1) {
                    currentRow.remove(maxIdx);
                }
                // Keep track of the max among deleted elements for this step
                if (maxVal > maxOfDeleted) {
                    maxOfDeleted = maxVal;
                }
            }
            result += maxOfDeleted;
        }
        return result;
    }
}
```
### Algorithm
- Convert the input `int[][]` grid into a `List<List<Integer>>` to make element removal easier.
- Initialize a variable `result = 0`.
- Loop `n` times, where `n` is the number of columns.
- In each loop iteration (representing one step of the operation):
  - Initialize a variable `maxOfDeletedInStep = 0`.
  - Iterate through each row of the list-based grid.
  - In each row, find the maximum value and its index.
  - Update `maxOfDeletedInStep = max(maxOfDeletedInStep, found_max_value)`.
  - Remove the element at the found index from the row.
  - After iterating through all rows, add `maxOfDeletedInStep` to the `result`.
- Return `result` after the main loop completes.

## Sort Each Row and Traverse Columns
A much more efficient approach comes from a key insight: the sequence of deleted elements from any given row is simply the elements of that row sorted in descending order. Therefore, instead of simulating the deletion, we can sort each row first. Once all rows are sorted, the problem transforms into finding the maximum value in each column and summing these maximums up.
**Time:** O(m * n log n). The dominant operation is sorting. We sort `m` rows, and sorting each row of size `n` takes `O(n log n)`. The subsequent traversal of the grid to find column-wise maximums takes `O(m * n)`, which is less than the sorting time. Thus, the total complexity is `O(m * n log n)`. · **Space:** O(log n) or O(n). This space is used by the recursion stack of the in-place sorting algorithm (`Arrays.sort` in Java uses a dual-pivot quicksort). The space complexity is O(log n) on average and O(n) in the worst case. No other significant auxiliary space is needed.
**Pros:** Significantly more efficient with a time complexity of O(m * n log n).; The logic is clean and avoids complex data structure manipulations for deletion.; Minimal auxiliary space is required if in-place modification of the grid is allowed.
**Cons:** This approach modifies the input grid. If the original grid needs to be preserved, a copy must be made first, which would increase the space complexity to O(m*n).
### Explanation
The core idea is to reframe the problem to avoid the costly simulation of deletions. The set of elements removed from a row over all steps is just the entire set of elements in that row. The order of removal is from greatest to smallest.

By sorting each row of the grid (e.g., in ascending order), we arrange the elements such that all the largest values are in the last column (`n-1`), all the second-largest values are in the second-to-last column (`n-2`), and so on. The smallest values for each row will be in the first column (`0`).

The operation described in the problem can now be viewed column by column on this sorted grid. The first step of the operation corresponds to finding the maximum among the elements in the last column of the sorted grid. The second step corresponds to the second-to-last column, and so on. We can simply iterate through the columns, find the maximum value in each, and add it to our total sum.

```java
import java.util.Arrays;

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // Step 1: Sort each row
        for (int i = 0; i < m; i++) {
            Arrays.sort(grid[i]);
        }

        int answer = 0;
        // Step 2: Iterate through columns of the sorted grid
        for (int j = 0; j < n; j++) {
            int maxInCol = 0;
            // Step 3: Find the max in the current column
            for (int i = 0; i < m; i++) {
                if (grid[i][j] > maxInCol) {
                    maxInCol = grid[i][j];
                }
            }
            // Step 4: Add the column's max to the answer
            answer += maxInCol;
        }

        return answer;
    }
}
```
### Algorithm
- Iterate through each of the `m` rows in the `grid`.
- For each row, sort its elements in ascending order using `Arrays.sort()`.
- After sorting, `grid[i][j]` contains the (j+1)-th smallest element of the original row `i`.
- Initialize a variable `answer = 0`.
- Iterate through the columns from `j = 0` to `n-1`.
- For each column `j`:
  - Initialize a variable `maxInCol = 0`.
  - Iterate through the rows from `i = 0` to `m-1` to find the maximum value in the current column `j`.
  - Update `maxInCol = max(maxInCol, grid[i][j])`.
  - Add `maxInCol` to the `answer`.
- Return the final `answer`.

# Solutions
### Java

```java
class Solution {
public
  int deleteGreatestValue(int[][] grid) {
    for (var row : grid) {
      Arrays.sort(row);
    }
    int ans = 0;
    for (int j = 0; j < grid[0].length; ++j) {
      int t = 0;
      for (int i = 0; i < grid.length; ++i) {
        t = Math.max(t, grid[i][j]);
      }
      ans += t;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int deleteGreatestValue(vector<vector<int>> &grid) {
    for (auto &row : grid)
      sort(row.begin(), row.end());
    int ans = 0;
    for (int j = 0; j < grid[0].size(); ++j) {
      int t = 0;
      for (int i = 0; i < grid.size(); ++i) {
        t = max(t, grid[i][j]);
      }
      ans += t;
    }
    return ans;
  }
};

```

### Python

```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))

```