Sum of Matrix After Queries

Problem Description

You are given an integer n and a 0-indexed 2D array queries where queries[i] = [type_i, index_i, val_i]. Initially, there is a 0-indexed n x n matrix filled with 0's. For each query, you must apply one of the following changes:

• if type_i == 0, set the values in the row with index_i to val_i, overwriting any previous values.
• if type_i == 1, set the values in the column with index_i to val_i, overwriting any previous values.

Return the sum of integers in the matrix after all queries are applied.

Key Insights

• Each query either updates an entire row or an entire column.
• The last operation on any row or column dictates its final value.
• We can track the most recent update for each row and column separately to calculate the final sum efficiently.

Space and Time Complexity

Time Complexity: O(n + q), where n is the size of the matrix and q is the number of queries.
Space Complexity: O(n), for storing the last updated values for rows and columns.

Solution

To solve the problem, we will maintain two arrays: one for the most recent updates to each row and one for each column. Alongside these, we will keep track of the latest time when each row or column was updated. After processing all queries, we will calculate the final sum of the matrix based on the latest updates recorded.

1. Initialize two arrays rowUpdates and colUpdates to store the last value set for each row and column respectively.
2. Initialize two arrays rowTimes and colTimes to store the time of the last update for each row and column respectively.
3. Iterate over the queries and update these arrays based on the type of query.
4. Calculate the final sum of the matrix by considering the latest updates for each row and column.

Code Solutions