2718. Sum of Matrix After Queries

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:

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 <= 104
• 1 <= queries.length <= 5 * 104
• queries[i].length == 3
• 0 <= typei <= 1
• 0 <= indexi&nbsp;< n
• 0 <= vali <= 105

Solution (Java)

class Solution {
  public long matrixSumQueries(int n, int[][] queries) {
    var rows = new boolean[n];
    var cols = new boolean[n];
    int rowCnt = n, colCnt = n;
    var sum = 0L;

    for (var i = queries.length - 1; i >=0 && rowCnt > 0 && colCnt > 0; i--) {
      if (queries[i][0] == 0) {
        if (rows[queries[i][1]]) continue;

        rows[queries[i][1]] = true;
        rowCnt--;
        sum += colCnt * queries[i][2];
      } else {
        if (cols[queries[i][1]]) continue;

        cols[queries[i][1]] = true;
        colCnt--;
        sum += rowCnt * queries[i][2];
      }
    }
    return sum;
  }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).