Description Link to heading

2718. Sum of Matrix After Queries (Medium) You are given an integer n and a 0-indexed 2D array queries where queries[i] = [typeᵢ, indexᵢ, valᵢ].

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ᵢ == 0, set the values in the row with indexᵢ to valᵢ, overwriting any previous values.
  • if typeᵢ == 1, set the values in the column with indexᵢ to valᵢ, overwriting any previous values.

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

Example 1:

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:

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 <= 10⁴
  • 1 <= queries.length <= 5 * 10⁴
  • queries[i].length == 3
  • 0 <= typeᵢ <= 1
  • 0 <= indexᵢ < n
  • 0 <= valᵢ <= 10⁵

Solution Link to heading

This problem is the third question in Leetcode’s 348th contest. At that time, I was struggling with it for a long time and felt foolish. I kept thinking that I needed to use some advanced data structure. However, it turns out that it’s not that difficult; the main challenge is to think differently.

Essentially, this problem is a simulation task. However, if we follow the given instructions and simulate the process in ascending order, making incremental modifications and adjustments, we will fall into a trap and inevitably exceed the time limit.

To approach the problem from a different angle, we can try simulating it in reverse order. By doing so, we don’t need to worry about overwriting. Instead, we only need to consider how many cells to fill during row or column filling.

We can use a hash table to keep track of the unfilled rows or columns. During the reverse traversal, if we find that the current row has already been filled, we skip it. Otherwise, we add the product of $val \times k$ to $total$, where $k$ represents the number of unfilled columns. The process for column filling is similar.

Code Link to heading 

class Solution {
  public:
    long long matrixSumQueries(int n, vector<vector<int>> &queries) {
        unordered_set<int> col_hash, row_hash;
        for (int i = 0; i < n; ++i) {
            col_hash.insert(i);
            row_hash.insert(i);
        }
        int m = queries.size();
        long long total = 0;
        for (int i = m - 1; i >= 0 && !col_hash.empty() && !row_hash.empty(); --i) {
            if (queries[i][0] == 0) {
                if (row_hash.find(queries[i][1]) == row_hash.end()) {
                    continue;
                }
                total += col_hash.size() * queries[i][2];
                row_hash.erase(queries[i][1]);
            } else {
                if (col_hash.find(queries[i][1]) == col_hash.end()) {
                    continue;
                }
                total += row_hash.size() * queries[i][2];
                col_hash.erase(queries[i][1]);
            }
        }
        return total;
    }
};