# Sum of Matrix After Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-matrix-after-queries)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-matrix-after-queries
**Data structures:** Array, Hash Table
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
You are given an integer `n` and a **0-indexed** **2D array** `queries` where `queries[i] = [typei, indexi, vali]`.

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 `typei == 0`, set the values in the row with `indexi` to `vali`, overwriting any previous values.
* if `typei == 1`, set the values in the column with `indexi` to `vali`, overwriting any previous values.

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

**Example 1:**

![](https://assets.glich.co/dsa/sum-of-matrix-after-queries/image0.png) 

**Input:** n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
**Output:** 23
**Explanation:** The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 23. 

**Example 2:**

![](https://assets.glich.co/dsa/sum-of-matrix-after-queries/image1.png) 

**Input:** n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
**Output:** 17
**Explanation:** The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 17.

**Constraints:**

* `1 <= n <= 104`
* `1 <= queries.length <= 5 * 104`
* `queries[i].length == 3`
* `0 <= typei <= 1`
* `0 <= indexi < n`
* `0 <= vali <= 105`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It involves creating an `n x n` matrix and applying each query one by one by updating the corresponding row or column. After all queries are applied, it calculates the sum of all elements in the matrix by iterating through it.
**Time:** O(q * n + n^2) - Let `q` be the number of queries. Each query requires iterating through `n` elements, leading to O(q * n) for processing all queries. The final summation takes O(n^2). For the given constraints, this is too slow and will time out. · **Space:** O(n^2) - We need to store the entire `n x n` matrix in memory. For `n = 10^4`, this would be `10^8` integers, which is about 400MB and might exceed memory limits.
**Pros:** Simple to understand and implement.; Directly follows the problem statement, making the logic easy to verify.
**Cons:** Highly inefficient in both time and space for the given constraints.; Will likely result in Time Limit Exceeded (TLE) due to the O(q * n) complexity.; May result in Memory Limit Exceeded (MLE) for large `n` due to the O(n^2) space requirement.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It follows the problem description literally.

First, we create an actual `n x n` matrix and initialize all its cells to zero. Then, we iterate through the list of queries. For each query, we perform the specified operation: if it's a row update, we iterate through that entire row and set each cell to the given value; if it's a column update, we do the same for the specified column. After executing all the queries, we perform a final pass over the entire matrix to sum up all the cell values to get the result.

```java
class Solution {
    public long matrixSumQueries(int n, int[][] queries) {
        int[][] matrix = new int[n][n];
        for (int[] query : queries) {
            int type = query[0];
            int index = query[1];
            int val = query[2];
            if (type == 0) { // Row update
                for (int j = 0; j < n; j++) {
                    matrix[index][j] = val;
                }
            } else { // Column update
                for (int i = 0; i < n; i++) {
                    matrix[i][index] = val;
                }
            }
        }

        long sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += matrix[i][j];
            }
        }
        return sum;
    }
}
```
### Algorithm
- Initialize an `n x n` matrix, `grid`, with all elements set to 0.
- Iterate through each query `[type, index, val]` in the `queries` array.
- If `type` is 0, it's a row update. Iterate through all columns `j` from 0 to `n-1` and set `grid[index][j] = val`.
- If `type` is 1, it's a column update. Iterate through all rows `i` from 0 to `n-1` and set `grid[i][index] = val`.
- After processing all queries, initialize a variable `sum` to 0.
- Iterate through the entire `grid` (both rows and columns) and add each element's value to `sum`.
- Return the final `sum`.

## Process Queries in Reverse
A much more efficient approach is to realize that later queries overwrite the effects of earlier ones. The final value of a cell is determined by the last query that affects its row or column. By processing the queries in reverse order, we can calculate the sum without building the matrix. We only need to consider the *first* time we encounter a row or column (when iterating backward), as this corresponds to the *last* update applied to it. We keep track of which rows and columns have been 'set' and calculate their contribution to the total sum.
**Time:** O(q) - We iterate through the `queries` array once. Each operation inside the loop is constant time. · **Space:** O(n) - We use two boolean arrays of size `n` to keep track of seen rows and columns.
**Pros:** Highly efficient in both time and space.; Avoids creating the large `n x n` matrix, thus saving significant memory.; Easily passes the given constraints.
**Cons:** The logic is less direct than the brute-force approach and requires the key insight of processing queries in reverse.; Requires careful handling of counts to correctly calculate the contribution of each query.
### Explanation
The key observation is that the final state of the matrix only depends on the last query that sets a given row or column. Instead of simulating the process forward, we can determine the final sum by processing queries backward.

We iterate from the last query to the first. We use two boolean arrays, `seenRow` and `seenCol`, to keep track of rows and columns for which we've already determined their final value. When we process a query for a row (or column) that we haven't seen yet, we know this is its final state. The value `val` from this query will be applied to all cells in that row (or column) that are not overwritten by an even later query (which, in our backward pass, means a column/row we've already processed).

For a row query `[0, index, val]`, if `seenRow[index]` is false, we add `val * (n - colCount)` to our total sum, where `colCount` is the number of columns we've already seen and finalized. We then mark this row as seen. A similar logic applies to column queries.

```java
class Solution {
    public long matrixSumQueries(int n, int[][] queries) {
        boolean[] seenRow = new boolean[n];
        boolean[] seenCol = new boolean[n];
        int rowCount = 0;
        int colCount = 0;
        long totalSum = 0;

        // Iterate backwards from the last query
        for (int i = queries.length - 1; i >= 0; i--) {
            int type = queries[i][0];
            int index = queries[i][1];
            int val = queries[i][2];

            if (type == 0) { // Row query
                if (!seenRow[index]) {
                    // This is the last update for this row.
                    // The number of cells in this row that are not yet set by a later column query is n - colCount.
                    totalSum += (long) val * (n - colCount);
                    seenRow[index] = true;
                    rowCount++;
                }
            } else { // Column query
                if (!seenCol[index]) {
                    // This is the last update for this column.
                    // The number of cells in this column that are not yet set by a later row query is n - rowCount.
                    totalSum += (long) val * (n - rowCount);
                    seenCol[index] = true;
                    colCount++;
                }
            }
        }

        return totalSum;
    }
}
```
### Algorithm
- Initialize two boolean arrays, `seenRow` of size `n` and `seenCol` of size `n`, to all `false`. These will track which rows/columns have been finalized.
- Initialize `totalSum = 0`, `rowCount = 0` (count of finalized rows), and `colCount = 0` (count of finalized columns).
- Iterate through the `queries` array in reverse order (from `queries.length - 1` down to `0`).
- For each query `[type, index, val]`:
  - If it's a row query (`type == 0`) and `seenRow[index]` is `false`:
    - This is the last update for this row. Its contribution to the sum is `val` multiplied by the number of columns not yet finalized, which is `n - colCount`.
    - Add `(long) val * (n - colCount)` to `totalSum`.
    - Mark the row as seen: `seenRow[index] = true`, and increment `rowCount`.
  - If it's a column query (`type == 1`) and `seenCol[index]` is `false`:
    - This is the last update for this column. Its contribution is `val` multiplied by the number of rows not yet finalized, `n - rowCount`.
    - Add `(long) val * (n - rowCount)` to `totalSum`.
    - Mark the column as seen: `seenCol[index] = true`, and increment `colCount`.
- After the loop finishes, `totalSum` will hold the final sum of the matrix.

# Solutions
### Java

```java
class Solution {
public
  long matrixSumQueries(int n, int[][] queries) {
    Set<Integer> row = new HashSet<>();
    Set<Integer> col = new HashSet<>();
    int m = queries.length;
    long ans = 0;
    for (int k = m - 1; k >= 0; --k) {
      var q = queries[k];
      int t = q[0], i = q[1], v = q[2];
      if (t == 0) {
        if (row.add(i)) {
          ans += 1L * (n - col.size()) * v;
        }
      } else {
        if (col.add(i)) {
          ans += 1L * (n - row.size()) * v;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long matrixSumQueries(int n, vector<vector<int>> &queries) {
    unordered_set<int> row, col;
    reverse(queries.begin(), queries.end());
    long long ans = 0;
    for (auto &q : queries) {
      int t = q[0], i = q[1], v = q[2];
      if (t == 0) {
        if (!row.count(i)) {
          ans += 1LL * (n - col.size()) * v;
          row.insert(i);
        }
      } else {
        if (!col.count(i)) {
          ans += 1LL * (n - row.size()) * v;
          col.insert(i);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int: row = set() col = set() ans = 0 for t, i, v in queries[:: - 1]: if t == 0: if i not in row: ans += v * (n - len(col)) row . add(i) else: if i not in col: ans += v * (n - len(row)) col . add(i) return ans

```