MediumArrayHash TableUpdated Sep 2026

2718. Sum of Matrix After Queries

Asked at Salesforce

Difficulty

Medium

Time

O(q)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an integer n and a list of queries. Start with an n x n matrix where every cell is 0.

Each query is a triple [type, index, val]. If type is 0, fill the whole row at index with val. If type is 1, fill the whole column at index with val. A fill overwrites whatever was in those cells before, so later queries can erase earlier ones.

Apply all queries in the given order, then return the sum of every cell in the final matrix.

Rows and columns overwrite each other

start012012000000000The matrix starts as all zeros.after query 3012012413423433The last query paints column 0 with 4, so those threecells are 4.
Each query paints a full row or column, and the last paint on a cell wins.

Constraints

  • ●1 <= n <= 10^4
  • ●1 <= queries.length <= 5 * 10^4
  • ●queries[i].length == 3
  • ●0 <= typei <= 1
  • ●0 <= indexi < n
  • ●0 <= vali <= 10^5

Examples

Example 1
Inputn = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
Output23
WhyRow 0 becomes [1,1,1], then column 2 becomes [1,2,1], then row 2 becomes [3,3,3], then column 0 becomes [4,2,3]. The final matrix is [[4,1,3],[4,2,3],[4,3,3]] and its cells add up to 23.
Example 2
Inputn = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
Output17
WhyRow 0 becomes [4,4,4], row 1 becomes [2,2,2], column 0 becomes [1,2,3], row 2 becomes [3,3,3], then column 2 becomes [1,1,1]. The final matrix is [[1,4,1],[2,2,1],[3,3,1]] and its cells add up to 17.

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Brute force: For each query, iterate through the entire row or column and update each cell, then sum the matrix at the end.

2

Improved: Track which rows and columns have been set and when. Process queries in reverse order so the first set wins.

3

Better: Use a set to track already-updated rows and columns. When setting a row, only update cells in columns not yet set.

4

Refined: Process queries in reverse. For row queries, multiply val by columns not yet processed. For column queries, multiply val by rows not yet processed.

5

Optimal: Reverse iteration with two hash sets for updated rows and columns. For each query, count unaffected cells and accumulate sum. O(q + n) time, O(n) space.

Optimal Approach

Process queries in reverse order. Maintain two hash sets: one for rows already set and one for columns already set. For a row query [0, index, val], the number of cells whose value is determined by this query equals (n - number of columns already set). Add val times that count to the result. Similarly for column queries. After processing, mark the row or column as set. This works because reverse processing ensures that the first set operation encountered for any row or column is the one that will determine its final value in the matrix. Time: O(q + n), Space: O(n) where q is the number of queries.

Walk the queries backwards

seen_rows = {}, seen_cols = {}read queries from last to firstnew row: add val * (n - |seen_cols|)new col: add val * (n - |seen_rows|)A row query only decides the cells in columns that nolater column query has already claimed.row: val * (n - len(seen_cols))col: val * (n - len(seen_rows))skip if the row/col was already seen
Going in reverse, the first time we meet a row or column is exactly the value that survives in the final matrix.
ComplexityTime O(q)Space O(n)Each query is handled once in a single reverse pass, and the two sets hold at most n rows and n columns.

Solution Code

O(q) time
def matrixSumQueries(n, queries):
    result = 0
    seen_rows = set()
    seen_cols = set()
    for typ, idx, val in reversed(queries):
        if typ == 0:
            if idx not in seen_rows:
                result += val * (n - len(seen_cols))
                seen_rows.add(idx)
        else:
            if idx not in seen_cols:
                result += val * (n - len(seen_rows))
                seen_cols.add(idx)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Sum of Matrix After Queries problem?

Given an n x n matrix initialized with all zeros and a list of queries where each query is of the form [type, index, val], apply the queries in order and return the sum of all values in the matrix. Type 0 sets the row at index to val, and type 1 sets the column at index to val.

How do you solve Sum of Matrix After Queries?

The optimal approach runs in O(q) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Sum of Matrix After Queries?

Sum of Matrix After Queries is asked at Salesforce. It is a medium difficulty problem.