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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum in a Matrix

Difficulty: Medium

Problem Description

You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:

  1. From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
  2. Identify the highest number amongst all those removed in step 1. Add that number to your score.

Return the final score.

Key Insights

  • Each row contributes its maximum value to the score in every iteration until the matrix is empty.
  • We need to repeatedly find and remove the maximum value from each row, which can be efficiently managed.
  • The problem can be solved using a priority queue (heap) to keep track of the largest numbers removed from each row.

Space and Time Complexity

Time Complexity: O(m * n log n), where m is the number of rows and n is the maximum number of columns, due to the repeated extraction of maximum values from each row. Space Complexity: O(m), for storing the maximum values removed from each row.

Solution

To solve the problem, we will repeatedly remove the maximum element from each row of the matrix until all elements are removed. We will maintain a score that accumulates the highest maximum extracted in each iteration. A max-heap can help us efficiently track and retrieve the largest numbers from each row.

  1. For each row, find and remove the largest element.
  2. Keep track of these maximums and determine the largest among them.
  3. Add this largest value to the score.
  4. Repeat the process until the matrix is empty.

Code Solutions

def sumInMatrix(nums):
    score = 0
    while nums:  # Continue until nums is empty
        max_values = []
        for row in nums:
            max_value = max(row)  # Find the maximum in the current row
            max_values.append(max_value)
            row.remove(max_value)  # Remove the maximum element from the row
        score += max(max_values)  # Add the highest maximum to the score
        nums = [row for row in nums if row]  # Remove empty rows
    return score
← Back to All Questions