Delete Greatest Value in Each Row — LeetCode 2500 Python Solution

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

Example

Input

grid = [[1,2,4],[3,3,1]]

Output

8

Explanation

The diagram above shows the removed values in each step.

Python solution

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

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2500. Delete Greatest Value in Each Row is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems