Problem Description

You start with an n x n matrix where all values are initially 0. You're given a list of queries, where each query has three components: [type, index, val].

For each query, you need to perform one of two operations:

• If type = 0: Set all values in row index to val (overwriting any previous values in that row)
• If type = 1: Set all values in column index to val (overwriting any previous values in that column)

After processing all queries in order, return the sum of all values in the final matrix.

The key insight is that when multiple queries affect the same cell, only the last query matters for that cell's final value. For example, if row 0 is set to value 5, then column 0 is set to value 3, the cell at position (0,0) will have value 3 (from the later column operation).

The solution works backwards through the queries. By processing queries in reverse order, we can track which rows and columns have already been "finalized" (since we're going backwards, the first time we see a row or column is actually its last modification).

When processing a row query for row i with value v:

• If row i hasn't been seen yet, it contributes v * (n - |already_finalized_columns|) to the sum
• The (n - |already_finalized_columns|) part counts how many cells in this row haven't been finalized by a later column operation

Similarly for column queries:

• If column i hasn't been seen yet, it contributes v * (n - |already_finalized_rows|) to the sum

This approach efficiently calculates the final sum without actually building the matrix, by recognizing that each cell's value comes from the last query that affected it.

Intuition

The first observation is that if we were to simulate the queries directly by updating the matrix, we'd be overwriting values multiple times unnecessarily. For any given cell, only the last operation that affects it determines its final value.

Consider a cell at position (r, c). This cell could be modified by:

• Any query that sets row r to some value
• Any query that sets column c to some value

Among all these queries, only the last one in the sequence matters for the final value of this cell.

This leads to a key insight: instead of processing queries forward and overwriting values, we can process them backwards. When going backwards:

• The first time we encounter a row i, we know this is actually the last modification to that row
• The first time we encounter a column j, we know this is actually the last modification to that column

Now, when we process a row query (0, i, v) going backwards:

• If we haven't seen row i before, this query sets the final values for row i
• But some cells in row i might already have their final values set by column queries we've already processed (remember, we're going backwards)
• So row i contributes v * (number of cells not yet finalized by columns) = v * (n - |columns_already_seen|)

The same logic applies to column queries.

By using two sets to track which rows and columns we've already processed (going backwards), we can calculate the exact contribution of each query to the final sum without actually building the matrix. This transforms an O(n² * q) problem (if we simulated directly) into an O(q) solution where q is the number of queries.

Solution Approach

The implementation uses two hash sets and processes queries in reverse order:

Data Structures:

• row: A set to track which rows have been finalized (processed while going backwards)
• col: A set to track which columns have been finalized
• ans: Accumulator for the final sum

Algorithm Steps:

1. Initialize empty sets for row and col, and set ans = 0

2. Reverse iterate through queries using queries[::-1]:

   For each query (t, i, v):

   • If t == 0 (row operation):
     • Check if row i is already in the row set
     • If not (this is the last modification to row i):
       • Add v * (n - len(col)) to the answer
       • The term (n - len(col)) represents the number of cells in row i that haven't been finalized by column operations
       • Add i to the row set to mark it as processed
   • If t == 1 (column operation):
     • Check if column i is already in the col set
     • If not (this is the last modification to column i):
       • Add v * (n - len(row)) to the answer
       • The term (n - len(row)) represents the number of cells in column i that haven't been finalized by row operations
       • Add i to the col set to mark it as processed

3. Return the accumulated sum

Key Insight: When processing a row query backwards, the cells that contribute to the sum are those not yet claimed by column queries. Since len(col) tells us how many columns have been finalized, n - len(col) gives us the count of cells in the current row that will take the value v.

Time Complexity: O(q) where q is the number of queries, as we process each query once.

Space Complexity: O(min(n, q)) for storing the row and column sets, bounded by either the matrix dimension or the number of queries.

Example Walkthrough

Let's walk through a concrete example with a 3×3 matrix and the following queries:

• Query 0: [0, 0, 2] - Set row 0 to value 2
• Query 1: [1, 1, 3] - Set column 1 to value 3
• Query 2: [0, 0, 5] - Set row 0 to value 5
• Query 3: [1, 2, 4] - Set column 2 to value 4

Step 1: Understand the final matrix If we applied these queries forward, the matrix would look like:

After Query 0: [2,2,2]    After Query 1: [2,3,2]    After Query 2: [5,3,5]    After Query 3: [5,3,4]
               [0,0,0]                   [0,3,0]                   [0,3,0]                   [0,3,4]
               [0,0,0]                   [0,3,0]                   [0,3,0]                   [0,3,4]

Final sum = 5 + 3 + 4 + 0 + 3 + 4 + 0 + 3 + 4 = 26

Step 2: Process queries backwards

Initialize: row = {}, col = {}, ans = 0, n = 3

Processing Query 3: [1, 2, 4] (column 2 = 4)

• Column 2 not in col set → this is the last modification to column 2
• Contribution: 4 × (3 - 0) = 12 (all 3 cells in column 2)
• Update: col = {2}, ans = 12

Processing Query 2: [0, 0, 5] (row 0 = 5)

• Row 0 not in row set → this is the last modification to row 0
• Contribution: 5 × (3 - 1) = 10 (2 cells: columns 0 and 1, since column 2 already finalized)
• Update: row = {0}, ans = 22

Processing Query 1: [1, 1, 3] (column 1 = 3)

• Column 1 not in col set → this is the last modification to column 1
• Contribution: 3 × (3 - 1) = 6 (2 cells: rows 1 and 2, since row 0 already finalized)
• Update: col = {1, 2}, ans = 28

Processing Query 0: [0, 0, 2] (row 0 = 2)

• Row 0 already in row set → skip (Query 2 was the last modification to row 0)
• No contribution
• ans = 28

Wait, our answer is 28 but expected is 26. Let me recalculate...

Actually, I made an error. Let me recalculate the final matrix:

• Cell (0,0): Last affected by Query 2 (row 0 = 5) → value = 5
• Cell (0,1): Last affected by Query 2 (row 0 = 5) → value = 5
• Cell (0,2): Last affected by Query 3 (col 2 = 4) → value = 4
• Cell (1,0): Never modified → value = 0
• Cell (1,1): Last affected by Query 1 (col 1 = 3) → value = 3
• Cell (1,2): Last affected by Query 3 (col 2 = 4) → value = 4
• Cell (2,0): Never modified → value = 0
• Cell (2,1): Last affected by Query 1 (col 1 = 3) → value = 3
• Cell (2,2): Last affected by Query 3 (col 2 = 4) → value = 4

Final matrix:

[5, 5, 4]
[0, 3, 4]
[0, 3, 4]

Sum = 5 + 5 + 4 + 0 + 3 + 4 + 0 + 3 + 4 = 28

The backward processing correctly calculated 28 as the sum, demonstrating how the algorithm efficiently computes the result without building the actual matrix.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(m), where m is the number of queries. This is because:

• The code iterates through the queries list once in reverse order using queries[::-1], which takes O(m) time to create the reversed list
• For each query, the operations performed are:
  • Checking membership in a set (i not in row or i not in col): O(1) average case
  • Adding an element to a set (row.add(i) or col.add(i)): O(1) average case
  • Getting the length of a set (len(col) or len(row)): O(1)
  • Basic arithmetic operations: O(1)
• Since we perform O(1) operations for each of the m queries, the total time complexity is O(m)

The space complexity is O(n), where n is the dimension of the matrix. This is because:

• The row set can contain at most n elements (one for each row index from 0 to n-1)
• The col set can contain at most n elements (one for each column index from 0 to n-1)
• The reversed queries list queries[::-1] takes O(m) space, but since the problem constraints typically have m ≤ n² and we're tracking which rows/columns have been modified (at most n each), the dominant space factor is O(n)
• Other variables (ans, t, i, v) use O(1) space

Therefore, the overall space complexity is O(n).

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

Common Pitfalls

1. Processing Queries in Forward Order

A major pitfall is attempting to process queries from beginning to end. This leads to incorrect results because you'd need to track and update overlapping cells multiple times.

Wrong Approach:

# INCORRECT - Processing forward
total_sum = 0
for query_type, index, value in queries:  # Forward iteration
    if query_type == 0:
        # This doesn't account for future overrides
        total_sum += value * n

Solution: Always process queries in reverse order using queries[::-1] since the last query affecting a cell determines its final value.

2. Incorrect Calculation of Unfilled Cells

When calculating how many cells a row/column operation affects, forgetting that some cells are already finalized by perpendicular operations.

Wrong Approach:

if index not in processed_rows:
    total_sum += value * n  # INCORRECT - assumes all n cells are affected

Solution: Subtract the number of already-processed perpendicular lines:

if index not in processed_rows:
    total_sum += value * (n - len(processed_cols))  # Correct

3. Confusing Row vs Column Logic

Mixing up which set to check when processing different query types.

Wrong Approach:

if query_type == 0:  # Row operation
    if index not in processed_cols:  # WRONG - checking columns for row operation
        total_sum += value * (n - len(processed_rows))  # WRONG calculation

Solution: Match the query type with the appropriate set:

• Row operations (type 0): Check processed_rows, subtract len(processed_cols)
• Column operations (type 1): Check processed_cols, subtract len(processed_rows)

4. Not Handling Edge Cases

Failing to consider when all rows or columns have been processed before all queries are examined.

Solution: The current implementation naturally handles this - when len(processed_cols) == n or len(processed_rows) == n, the contribution becomes 0, which is correct since no new cells can be affected.