We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Greatest Value in Each Row

Number: 2585

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an m x n matrix grid consisting of positive integers, perform the following operations until grid becomes empty:

  • From each row, delete an element with the greatest value. (If there are ties, you may delete any of them.)
  • Add the maximum of the deleted elements (from all rows) to an answer. Note that the number of columns decreases by one after each round. Return the final answer after performing all operations.

Key Insights

  • Each row’s deletion operation simply removes its current maximum element.
  • Sorting every row in ascending order lets you simulate the rounds by picking elements from the end of each row.
  • In the i-th round (starting from 0), the element removed from a row is at index (n - 1 - i) after sorting.
  • The overall answer is the sum of the maximum value from each round across all rows.

Space and Time Complexity

Time Complexity: O(m * n * log n), due to sorting each row. Space Complexity: O(1) extra space (ignoring the input space).

Solution

Sort each row of the grid in ascending order so that the greatest element in any row is always at the end. Then simulate the rounds without actually removing elements: in the first round, the last element from each row (i.e. the maximum) is considered; in the second round, the second last element is taken, and so on. For each round, compute the maximum among these chosen elements and add it to the answer.

This approach leverages sorting and a simple iteration over columns (from last to first), avoiding the need for a more complex simulation of removals.

Code Solutions

# Define the function to delete the greatest element in each row and sum the round maxima
def deleteGreatestValue(grid):
    # Sort each row in ascending order
    for row in grid:
        row.sort()
    
    total_sum = 0
    n = len(grid[0])  # number of columns in the grid
    
    # For each round, iterate from the last column to the first
    for col in range(n - 1, -1, -1):
        round_max = 0
        # For every row, take the element at the current column index
        for row in grid:
            round_max = max(round_max, row[col])
        total_sum += round_max
    return total_sum

# Example usage: should output 8 for grid = [[1,2,4],[3,3,1]]
if __name__ == "__main__":
    grid = [[1, 2, 4], [3, 3, 1]]
    print(deleteGreatestValue(grid))
← Back to All Questions