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 of Matrix After Queries

Number: 2838

Difficulty: Medium

Paid? No

Companies: Sprinklr

Problem Description

Given an n x n matrix initially filled with 0's and a list of queries where each query either sets all values in a specified row or column to a given value, return the sum of all elements in the matrix after performing all the queries.

Key Insights

  • Direct simulation of each query is too slow due to large constraints (n up to 10^4 and queries up to 5 * 10^4).
  • Instead of simulating each update on all cells, one can calculate contributions of each query by processing the queries in reverse order.
  • Use boolean markers for rows and columns to check whether a row or column's value has been "finalized" by a later query.
  • When processing a query, if the target row or column hasn’t been updated later, its contribution is determined by the number of columns or rows that are still not finalized.
  • This reverse approach ensures that each cell is counted only once from the most recent query that updated it.

Space and Time Complexity

Time Complexity: O(Q), where Q is the number of queries
Space Complexity: O(n), for maintaining markers for n rows and n columns

Solution

The solution works by processing the queries from the last to the first. We maintain two boolean arrays (or sets) to track whether a particular row or column has already been updated by a query that is later in the operation sequence (when read in forward order).
For each query in reverse:

  • If the query updates a row and that row is not already marked, then add (value * number of columns still not updated) to the total sum and mark the row.
  • If the query updates a column and that column is not already marked, then add (value * number of rows still not updated) to the total sum and mark the column.

This method ensures that we only account for updates that are not subsequently overwritten.

Code Solutions

# Python solution
def matrixSumQueries(n, queries):
    # Initialize markers for rows and columns as not yet updated.
    row_updated = [False] * n
    col_updated = [False] * n
    total_sum = 0
    # Counters for rows and columns that have been updated.
    rows_remaining = n
    cols_remaining = n

    # Process the queries in reverse order.
    for qtype, index, value in reversed(queries):
        # If type 0, update row.
        if qtype == 0:
            if not row_updated[index]:
                # The row contributes value for each column not updated.
                total_sum += value * cols_remaining
                row_updated[index] = True
                rows_remaining -= 1
        # If type 1, update column.
        else:  # qtype == 1
            if not col_updated[index]:
                # The column contributes value for each row not updated.
                total_sum += value * rows_remaining
                col_updated[index] = True
                cols_remaining -= 1

    return total_sum

# Example usage:
n = 3
queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
print(matrixSumQueries(n, queries))  # Expected output: 23
← Back to All Questions