2718. Sum of Matrix After Queries

MediumArrayHash Table
Leetcode Link

Problem Description

In this problem, you are given two parameters. The first is an integer n, which indicates the size of a square matrix that you are to consider. This matrix is initially filled with zeroes and has dimensions n x n. The second parameter is queries, a 2D array where each element represents a specific action to be performed on the matrix. Each query has three elements:

  • type_i: indicates whether the action is to be performed on a row (0) or on a column (1).
  • index_i: the zero-based index of the row or column that the action is to be applied to.
  • val_i: the value that will replace the current contents of the specified row or column.

The goal of the problem is to apply each query to the matrix in the given order and then return the sum of all values in the matrix after all queries have been applied.

Intuition

To find the solution efficiently, we have to take into account that applying a query to a row or column may overwrite the values previously set by another query. One intuitive approach to avoid unnecessary computations is to start from the last query and move to the first, because once a whole row or column is overwritten, further modifications to it won't affect our final sum.

The algorithm uses two sets, row and col, to keep track of all the rows and columns that have already been affected by a query. This is important because if a row or column is modified multiple times, only the last modification (the one encountered first in our reverse iteration) will stick by the end.

For each query, starting from the last one towards the first, the algorithm does the following:

  • If the query is of type 0 (row modification) and the row hasn't been affected by any previous query, we add to our running sum ans the value v multiplied by the number of columns n minus the number of columns already affected. Then the row index i is added to the set row.

  • If the query is of type 1 (column modification) and the column hasn't been affected by any previous query, we similarly add to ans the value v multiplied by the number of rows n minus the number of rows already affected. The column index i is then added to the set col.

This ensures that each part of the matrix is counted exactly once, leading to an efficient computation of the total sum after applying all queries.

Solution Approach

The solution utilizes a set data structure for both rows and columns to keep track of which ones have already been updated. A set is a good choice here because it allows for constant time complexity O(1) operations for adding elements and checking membership.

Here's the algorithm in a detailed walk-through:

  1. Initialize two sets, row and col, and a variable ans to store the sum of the matrix's values.
  2. Iterate through the queries array in reverse order using for t, i, v in queries[::-1]:. This is crucial, as we only want to count the last change made to a row or column; reverse iteration ensures that we encounter the last update first for each row or column.
  3. If the query is to update a row (t == 0):
    • Check if the current row index i is not in the row set, which means it hasn't been updated before in this reverse iteration.
    • If the row hasn't been updated before, multiply the new value v by the number of columns n minus the number of columns that have already been updated (len(col)). This calculation only accounts for the cells that have not been modified by a column update.
    • Add the result to ans to increment the matrix sum.
    • Add the current row index i to the set row.
  4. If the query is to update a column (t == 1):
    • Check if the current column index i is not in the col set.
    • If the column hasn't been updated before, multiply the new value v by the number of rows n minus the number of rows that have already been updated (len(row)), accounting only for the cells not modified by a row update.
    • Add the result to ans.
    • Add the current column index i to the set col.
  5. After the loop concludes, ans will hold the final sum of all values in the matrix after applying all queries.
  6. Return the variable ans.

In summary, this approach effectively skips over any redundant modifications to rows and columns by keeping track of whether they have been touched by a query already or not. This Algorithm has a time complexity of roughly O(Q), where Q is the number of queries, since each query is processed in constant time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let us consider the following example to illustrate the solution approach:

Suppose our matrix dimensions n is 3, so we have a 3x3 matrix:

10 0 0
20 0 0
30 0 0

And we have the following queries array where each query is type_i index_i val_i:

1[
2 [0, 0, 5],  // Query 1: Update row 0 with value 5
3 [1, 2, 3],  // Query 2: Update column 2 with value 3
4 [0, 1, 4],  // Query 3: Update row 1 with value 4
5]

Following the solution algorithm:

  1. Initialize two sets row and col and a variable ans to 0.

  2. Start iterating from the last query. For this example, Query 3 is the first one to process in reverse order:

    • Query 3 is [0, 1, 4] (update row 1 with 4).
    • Since row 1 is not in the row set, compute 4 * (3 - len(col)) = 4 * 3 = 12 because no columns have been updated yet.
    • Add 12 to ans, which becomes 12.
    • Add row index 1 to the row set: row = {1}.
  3. Next, we have Query 2:

    • Query 2 is [1, 2, 3] (update column 2 with 3).
    • Since column 2 is not in the col set, compute 3 * (3 - len(row)) = 3 * (3 - 1) = 6 to account only for the non-modified rows.
    • Add 6 to ans, which becomes 18.
    • Add column index 2 to the col set: col = {2}.
  4. Lastly, process Query 1:

    • Query 1 is [0, 0, 5] (update row 0 with 5).
    • Since row 0 is not in the row set, compute 5 * (3 - len(col)) = 5 * (3 - 1) = 10 because column 2 is already updated.
    • Add 10 to ans, which becomes 28.
    • Add row index 0 to the row set: row = {0, 1}.
  5. Now that all queries are processed, ans is 28. This is our final sum.

  6. Return the final sum ans, which is 28.

The matrix after all queries have been applied looks like this:

15 5 3
24 4 3
30 0 3

The sum of all values in the matrix is 5 + 5 + 3 + 4 + 4 + 3 + 0 + 0 + 3 = 27. However, the algorithm calculated a sum of 28 since it doesn't account for overlapping modifications in the same row or column.

If this discrepancy is unexpected based on the problem statement, we would need to adjust the solution approach to ensure that the value of cells that are at the intersection of the updated row and updated column is not counted twice. The presence of the discrepancy suggests there is a nuance in the problem statement or example that needs to be reconciled with the proposed algorithm.

Solution Implementation

1class Solution:
2    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
3        # Initialize sets to track unique rows and columns that have been updated
4        updated_rows = set()
5        updated_columns = set()
6      
7        # Initialize the answer to 0
8        total_sum = 0
9      
10        # Process the queries in reverse order
11        for query_type, index, value in reversed(queries):
12            if query_type == 0:  # Query to update a row
13                # If the row has not been updated before
14                if index not in updated_rows:
15                    # Add the value to the sum for all columns that haven't been updated
16                    total_sum += value * (n - len(updated_columns))
17                    # Mark the row as updated
18                    updated_rows.add(index)
19            else:  # Query to update a column
20                # If the column has not been updated before
21                if index not in updated_columns:
22                    # Add the value to the sum for all rows that haven't been updated
23                    total_sum += value * (n - len(updated_rows))
24                    # Mark the column as updated
25                    updated_columns.add(index)
26      
27        # Return the total sum after processing all queries
28        return total_sum
29
1class Solution {
2  
3    /**
4     * Calculate the sum of all elements in a matrix after applying queries to increment rows/columns.
5     *
6     * @param n       The size of the matrix (n x n).
7     * @param queries An array of queries where each query contains three integers: [type, index, value].
8     *                Type 0 means add 'value' to a row at 'index', type 1 means add 'value' to a column at 'index'.
9     * @return The sum of all the elements in the matrix after applying all the queries.
10     */
11    public long matrixSumQueries(int n, int[][] queries) {
12        // Use hash sets to keep track of updated rows and columns to avoid repetitive additions.
13        Set<Integer> updatedRows = new HashSet<>();
14        Set<Integer> updatedColumns = new HashSet<>();
15      
16        // The total number of queries.
17        int totalQueries = queries.length;
18      
19        // This will hold the final sum of the matrix elements after applying the queries.
20        long totalSum = 0;
21      
22        // Iterate through the queries in reverse order.
23        for (int k = totalQueries - 1; k >= 0; --k) {
24            // Current query
25            int[] currentQuery = queries[k];
26            // Query type: 0 for row update, 1 for column update.
27            int queryType = currentQuery[0];
28            // Index of the row or column to update.
29            int index = currentQuery[1];
30            // Value to be added to the row or column.
31            int value = currentQuery[2];
32          
33            if (queryType == 0) {
34                // If it's a row update and the row hasn't been updated before
35                if (updatedRows.add(index)) {
36                    // Add value to each column in the row except those columns that have already been updated.
37                    totalSum += 1L * (n - updatedColumns.size()) * value;
38                }
39            } else {
40                // If it's a column update and the column hasn't been updated before
41                if (updatedColumns.add(index)) {
42                    // Add value to each row in the column except those rows that have already been updated.
43                    totalSum += 1L * (n - updatedRows.size()) * value;
44                }
45            }
46        }
47      
48        // Return the computed sum.
49        return totalSum;
50    }
51}
52
1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7    /* 
8    This function calculates the sum of matrix elements after applying a series of increment operations to all elements of specific rows or columns.
9    'n' is the size of the n x n matrix, where each element starts at 0.
10    'queries' is a vector of vector<int> containing the increment operations in the form of [type, index, value].
11    'type' specifies the operation type: 0 for row increment, 1 for column increment.
12    'index' specifies the row or column index to increment.
13    'value' is the amount by which to increment the specified row or column.
14    The function returns the resulting sum of the matrix after all increment operations have been applied.
15    */
16    long long matrixSumQueries(int n, vector<vector<int>>& queries) {
17        unordered_set<int> processedRows, processedCols; // Sets to track processed rows and columns
18        reverse(queries.begin(), queries.end()); // Reverse the order of queries to process from last to first
19        long long sum = 0; // Initialize the sum as a long long to avoid overflow
20      
21        // Loop over each query in the reversed queries
22        for (const auto& query : queries) {
23            int type = query[0]; // Type of operation (row or col increment)
24            int index = query[1]; // Index of row or column
25            int value = query[2]; // Value to add
26          
27            // Process row increment if type is 0
28            if (type == 0) {
29                // Check if the row hasn't been processed already
30                if (processedRows.count(index) == 0) {
31                    // Add to sum the value times the number of non-processed columns
32                    sum += static_cast<long long>(n - processedCols.size()) * value;
33                    // Mark the row as processed
34                    processedRows.insert(index);
35                }
36            } else { // Process column increment otherwise
37                // Check if the column hasn't been processed already
38                if (processedCols.count(index) == 0) {
39                    // Add to sum the value times the number of non-processed rows
40                    sum += static_cast<long long>(n - processedRows.size()) * value;
41                    // Mark the column as processed
42                    processedCols.insert(index);
43                }
44            }
45        }
46      
47        return sum; // Return the calculated sum
48    }
49};
50
1// Declares a function to calculate the sum of matrix elements based on provided queries.
2// n: the size of the square matrix.
3// queries: an array of queries where each query is an array containing a type (0 or 1),
4// an index i, and a value v.
5function matrixSumQueries(n: number, queries: number[][]): number {
6    // Initialize sets to keep track of processed rows and columns.
7    const processedRows: Set<number> = new Set();
8    const processedCols: Set<number> = new Set();
9    // Initialize the answer to store the sum of query results.
10    let answer = 0;
11
12    // Reverse the array of queries to process them in the last-in-first-out order.
13    queries.reverse();
14
15    // Iterate over each query in the reversed array.
16    for (const [type, index, value] of queries) {
17        if (type === 0) { // If the query type is '0', it targets a row.
18            if (!processedRows.has(index)) { // Check if the row hasn't been processed.
19                // Add the value times the number of unprocessed columns to the answer and mark the row as processed.
20                answer += value * (n - processedCols.size);
21                processedRows.add(index);
22            }
23        } else { // If the query type is '1', it targets a column.
24            if (!processedCols.has(index)) { // Check if the column hasn't been processed.
25                // Add the value times the number of unprocessed rows to the answer and mark the column as processed.
26                answer += value * (n - processedRows.size);
27                processedCols.add(index);
28            }
29        }
30    }
31
32    // Return the final calculated answer.
33    return answer;
34}
35

Time and Space Complexity

The provided code snippet appears to calculate the sum for a set of matrix sum queries. Each query consists of a type (t), an index (i), and a value (v). Based on the type of query, either an entire row or an entire column is updated (conceptually) with the value v, and the subsequent query computations take into account whether a row or column has already been updated to avoid double counting.

Time Complexity

The time complexity of the code can be determined by looking at the code within the for loop, which is executed once for each query. The for loop iterates over the queries in reverse order. For each query, the code checks whether the indexed row or column (indicated by i) has been previously updated by checking membership in the row and col sets.

The operations inside the loop, such as if i not in row and if i not in col, have an average-case time complexity of O(1) due to the constant-time complexity of set operations in Python for average cases. However, in the worst-case scenario (e.g. if hash collisions become frequent), these operations could degenerate to O(n) per operation.

When a row or column has not already been included in the row or col sets, the code performs a multiplication and an addition (v * (n - len(col)) or v * (n - len(row)), respectively). The multiplication and addition operations are O(1).

Since each query is only processed once, and the operations within the for loop are (on average) constant time, the average case time complexity of the entire code is O(m), where m is the number of queries. However, considering the worst-case scenario for the set operations, the time complexity could potentially be O(m * n).

Space Complexity

The space complexity consists of the space required to store the intermediate data structures row and col, in addition to the input size (the queries list).

  • The row and col sets collectively will store at most n elements each, assuming that all rows and all columns are eventually added to the sets.

The space complexity is therefore O(n) due to the sets row and col.

In summary:

  • Average-case time complexity: O(m), where m is the number of queries
  • Worst-case time complexity (considering potential set operation degradation): O(m * n), where m is the number of queries and n is the dimension of the square matrix (row/column size)
  • Space complexity: O(n), where n is the length or width of the square matrix

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄