Sum a Matrix After Row and Column Assignments
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Sum a Matrix After Row and Column Assignments
An `n x n` matrix starts with every entry equal to zero. You are given a 0-indexed array `queries`, where each query is `[type, index, val]`. Apply the queries in their listed order:
- If `type == 0`, set every entry in row `index` to `val`.
- If `type == 1`, set every entry in column `index` to `val`.
Each assignment overwrites previous values, including values set by queries of the other type. Return the sum of all matrix entries after every query has been applied.
### Examples
**Example 1**
```text
Input: n = 2, queries = [[1,0,5],[0,1,2],[1,0,1]]
Output: 4
```
The successive matrices are `[[5,0],[5,0]]`, `[[5,0],[2,2]]`, and `[[1,0],[1,2]]`. The final sum is `1 + 0 + 1 + 2 = 4`.
**Example 2**
```text
Input: n = 3, queries = [[0,1,7],[1,2,4],[0,1,0]]
Output: 8
```
The final assignment sets the entire middle row to zero. The final matrix is `[[0,0,4],[0,0,0],[0,0,4]]`, with sum `8`.
### Constraints
- `1 <= n <= 10^4`.
- `1 <= queries.length <= 5 * 10^4`.
- `queries[i].length == 3`.
- `0 <= type_i <= 1`.
- `0 <= index_i < n`.
- `0 <= val_i <= 10^5`.
### Clarifying Questions
- Do queries add `val` to existing entries? No; they replace the entries with `val`.
- Can a row or column be assigned more than once? Yes; later assignments overwrite earlier ones.
- Does assigning zero count as an overwrite? Yes; it can erase earlier nonzero values.
- Must the matrix itself be returned? No; return only its final sum.
### C++ Interface
```cpp
class Solution {
public:
long long matrixSumQueries(int n, vector<vector<int>>& queries) {
}
};
```
### Reasoning Checkpoints
- Decide which query determines a cell after all overwrites.
- Avoid constructing the full matrix at the largest allowed dimensions.
- Account for intersections between row and column assignments without counting a cell twice.
```hint Overwrite order
For a fixed cell, how do the timestamps of its row assignments and column assignments determine its final value?
```
Overview: Compute the final sum of an initially zero matrix after ordered row and column assignments, including repeated overwrites and zero-valued updates.