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

Sum in a Matrix

Number: 2728

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Given a 2D integer matrix called nums, you repeatedly perform the following operations until the matrix becomes empty:

  1. From each row that is not empty, remove the largest number.
  2. Of all removed numbers in that round, take the highest one and add it to your overall score. Return the final score after all operations.

Key Insights

  • Each row's largest remaining element is chosen at each round.
  • Sorting rows enables direct access to the largest elements without repeatedly scanning.
  • After sorting, the i-th round removes the i-th largest element of each row (if available).
  • The maximum among these removed elements is added to the score in each round.
  • Simulation is done by iterating through the sorted rows column-by-column from the end.

Space and Time Complexity

Time Complexity: O(n * m * log(m)) where n is the number of rows and m is the average number of columns; sorting each row dominates. Space Complexity: O(n * m) for storing the matrix, with additional space negligible.

Solution

We first sort each row in non-decreasing order. This step ensures that the largest elements are positioned at the end of every row. Then, rather than "simulating" removals dynamically, we iterate over possible rounds. In round i, for every row that has at least i elements, we consider its i-th largest element (i.e., element at index row_length - i). We compute the maximum of these elements across all rows and add this value to the overall score. This approach avoids costly repeated removals and efficiently computes the required score.

Code Solutions

# Python Code
def matrixSum(nums):
    # First, sort each row in non-decreasing order.
    for i in range(len(nums)):
        nums[i].sort()
    
    score = 0
    # The maximum number of rounds is determined by the longest row.
    max_rounds = max(len(row) for row in nums)
    
    # For each round from 1 to max_rounds, gather the i-th largest of each row.
    for round in range(1, max_rounds + 1):
        round_max = 0
        for row in nums:
            # If the row has enough elements, take its round-th largest element.
            if len(row) >= round:
                # The round-th largest element is at index -round.
                round_max = max(round_max, row[-round])
        # Add the maximum value of this round to the overall score.
        score += round_max
    return score

# Example usage:
print(matrixSum([[7,2,1],[6,4,2],[6,5,3],[3,2,1]]))  # Expected output: 15
← Back to All Questions