Sum of Matrix After Queries
Asked at Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Brute force: For each query, iterate through the entire row or column and update each cell, then sum the matrix at the end.
Improved: Track which rows and columns have been set and when. Process queries in reverse order so the first set wins.
Better: Use a set to track already-updated rows and columns. When setting a row, only update cells in columns not yet set.
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.
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sum of Matrix After Queries?
Sum of Matrix After Queries is asked at Salesforce. It is a medium difficulty problem.