Sum of Matrix After Queries — LeetCode 2718 Python Solution

The 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.

Example

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.

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2718. Sum of Matrix After Queries is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems