LeetCode Problem 2718

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

LeetCode 2718 - Sum of Matrix After Queries

Problem Understanding

The problem gives us an integer n representing the size of an n x n matrix. Initially, every cell in the matrix contains 0.

We are also given a list of queries. Each query has the form:

[type, index, value]

There are two kinds of operations:

• If type == 0, we overwrite every value in row index with value.
• If type == 1, we overwrite every value in column index with value.

Each operation completely replaces previous values in that row or column. Since later queries overwrite earlier ones, the final matrix depends heavily on the order of operations.

The task is to compute the sum of all values in the matrix after every query has been applied.

A straightforward simulation would explicitly update all affected cells for every query. However, the constraints are large:

• n can be up to 10^4
• queries.length can be up to 5 * 10^4

A full matrix can contain up to:

10^4 * 10^4 = 10^8 cells

That is far too large to repeatedly update directly.

The important observation is that we do not actually need the final matrix itself. We only need the final sum. This allows us to avoid storing the matrix entirely.

Some important edge cases include:

• Multiple updates to the same row or column
• Queries that overwrite previous operations completely
• Matrices of size 1 x 1
• Queries where value = 0
• Situations where every row or column is updated many times

The problem guarantees that indices are valid and all query formats are correct.

Approaches

Brute Force Approach

The brute force solution creates the full n x n matrix and applies every query directly.

For a row query:

• Update every column in that row

For a column query:

• Update every row in that column

After processing all queries, iterate through the entire matrix and compute the sum.

This works because it faithfully simulates the exact operations described in the problem statement.

However, the performance is too slow.

Each query may update up to n cells, and there can be up to 5 * 10^4 queries.

That leads to:

O(q * n)

operations just for updates, which can become:

5 * 10^4 * 10^4 = 5 * 10^8

Additionally, storing a 10^8 sized matrix is impractical.

Optimal Approach

The key insight is that later queries overwrite earlier ones.

Suppose we process queries in reverse order.

When we encounter a row update while moving backward:

• If that row has already been processed later, this query contributes nothing
• Otherwise, this query determines the final value for every column that has not already been fixed by a later column query

Similarly for columns.

This means:

• Each row only contributes once
• Each column only contributes once

We maintain:

• A set of rows already finalized
• A set of columns already finalized

When processing a row query in reverse:

contribution = value * remaining_unfixed_columns

When processing a column query in reverse:

contribution = value * remaining_unfixed_rows

This avoids constructing the matrix entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q * n + n²)	O(n²)	Explicitly simulates the matrix
Optimal	O(q)	O(n)	Processes queries in reverse using sets

Algorithm Walkthrough

1. Initialize two sets:

• visited_rows
• visited_cols

These track which rows and columns have already been finalized by later queries. 2. Initialize:

• remaining_rows = n
• remaining_cols = n

These count how many rows and columns are still unfixed. 3. Initialize total_sum = 0. 4. Traverse the queries in reverse order.

We go backward because the most recent assignment determines the final value. 5. For each query:

• Extract query_type, index, and value.

6. If the query updates a row:

• Check whether this row has already been processed.

• If yes, skip it because a later query already overwrote it.

• Otherwise:

• This row contributes value * remaining_cols

• Add that contribution to the answer

• Mark the row as visited

• Decrease remaining_rows

7. If the query updates a column:

• Check whether this column has already been processed.

• If yes, skip it.

• Otherwise:

• This column contributes value * remaining_rows

• Add that contribution to the answer

• Mark the column as visited

• Decrease remaining_cols

8. After all queries are processed, return total_sum.

Why it works

Processing in reverse guarantees that the first time we encounter a row or column is actually its final assignment in the original order.

For a row update, only columns that have not already been fixed by later column updates will retain this row's value. The same logic applies symmetrically for columns.

Because every cell's final value is counted exactly once, the computed sum is correct.

Python Solution

from typing import List

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        visited_rows = set()
        visited_cols = set()

        remaining_rows = n
        remaining_cols = n

        total_sum = 0

        for query_type, index, value in reversed(queries):

            # Row update
            if query_type == 0:
                if index in visited_rows:
                    continue

                total_sum += value * remaining_cols
                visited_rows.add(index)
                remaining_rows -= 1

            # Column update
            else:
                if index in visited_cols:
                    continue

                total_sum += value * remaining_rows
                visited_cols.add(index)
                remaining_cols -= 1

        return total_sum

The implementation directly follows the reverse-processing strategy.

Two sets are used to record which rows and columns have already received their final value.

The variables remaining_rows and remaining_cols are important because they tell us how many cells are still affected by a newly encountered reverse query.

When processing a row query:

total_sum += value * remaining_cols

This works because only columns not already overwritten by later column queries will keep this row's value.

Similarly, for a column query:

total_sum += value * remaining_rows

Each row and column is processed at most once, making the algorithm very efficient.

Go Solution

func matrixSumQueries(n int, queries [][]int) int64 {
    visitedRows := make(map[int]bool)
    visitedCols := make(map[int]bool)

    remainingRows := n
    remainingCols := n

    var totalSum int64 = 0

    for i := len(queries) - 1; i >= 0; i-- {
        queryType := queries[i][0]
        index := queries[i][1]
        value := queries[i][2]

        // Row update
        if queryType == 0 {
            if visitedRows[index] {
                continue
            }

            totalSum += int64(value * remainingCols)
            visitedRows[index] = true
            remainingRows--
        } else {
            // Column update
            if visitedCols[index] {
                continue
            }

            totalSum += int64(value * remainingRows)
            visitedCols[index] = true
            remainingCols--
        }
    }

    return totalSum
}

The Go solution mirrors the Python implementation closely.

Since Go does not have a built in set type, maps with boolean values are used:

map[int]bool

The answer uses int64 because the matrix sum can exceed the range of a 32 bit integer.

For example:

10^4 * 10^4 * 10^5 = 10^13

which requires 64 bit storage.

Worked Examples

Example 1

n = 3
queries = [
    [0,0,1],
    [1,2,2],
    [0,2,3],
    [1,0,4]
]

We process queries in reverse order.

Initial state:

Variable	Value
visited_rows	{}
visited_cols	{}
remaining_rows	3
remaining_cols	3
total_sum	0

Step 1

Query:

[1,0,4]

Column 0 has not been visited.

Contribution:

4 * remaining_rows
= 4 * 3
= 12

State after update:

Variable	Value
visited_cols	{0}
remaining_cols	2
total_sum	12

Step 2

Query:

[0,2,3]

Row 2 not visited.

Contribution:

3 * remaining_cols
= 3 * 2
= 6

State:

Variable	Value
visited_rows	{2}
remaining_rows	2
total_sum	18

Step 3

Query:

[1,2,2]

Column 2 not visited.

Contribution:

2 * remaining_rows
= 2 * 2
= 4

State:

Variable	Value
visited_cols	{0,2}
remaining_cols	1
total_sum	22

Step 4

Query:

[0,0,1]

Row 0 not visited.

Contribution:

1 * remaining_cols
= 1 * 1
= 1

Final answer:

22 + 1 = 23

Example 2

n = 3
queries = [
    [0,0,4],
    [0,1,2],
    [1,0,1],
    [0,2,3],
    [1,2,1]
]

Reverse order:

[1,2,1]
[0,2,3]
[1,0,1]
[0,1,2]
[0,0,4]

Step	Query	Contribution	Total
1	[1,2,1]	1 × 3 = 3	3
2	[0,2,3]	3 × 2 = 6	9
3	[1,0,1]	1 × 2 = 2	11
4	[0,1,2]	2 × 1 = 2	13
5	[0,0,4]	4 × 1 = 4	17

Final answer:

17

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q)	Each query is processed once
Space	O(n)	Sets store at most n rows and n columns

The algorithm scans the query list exactly one time in reverse order.

Each row and column is inserted into its corresponding set at most once, and set operations are average O(1) time.

No matrix is constructed, which avoids the massive memory usage of the brute force approach.

Test Cases

from typing import List

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        visited_rows = set()
        visited_cols = set()

        remaining_rows = n
        remaining_cols = n

        total_sum = 0

        for query_type, index, value in reversed(queries):

            if query_type == 0:
                if index in visited_rows:
                    continue

                total_sum += value * remaining_cols
                visited_rows.add(index)
                remaining_rows -= 1

            else:
                if index in visited_cols:
                    continue

                total_sum += value * remaining_rows
                visited_cols.add(index)
                remaining_cols -= 1

        return total_sum

sol = Solution()

assert sol.matrixSumQueries(
    3,
    [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
) == 23  # Provided example 1

assert sol.matrixSumQueries(
    3,
    [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
) == 17  # Provided example 2

assert sol.matrixSumQueries(
    1,
    [[0,0,5]]
) == 5  # Single cell matrix

assert sol.matrixSumQueries(
    1,
    [[0,0,5],[1,0,2]]
) == 2  # Later overwrite

assert sol.matrixSumQueries(
    2,
    [[0,0,1],[0,0,3]]
) == 6  # Same row updated multiple times

assert sol.matrixSumQueries(
    2,
    [[1,1,4],[1,1,2]]
) == 4  # Same column updated multiple times

assert sol.matrixSumQueries(
    2,
    [[0,0,0],[1,1,0]]
) == 0  # Zero values

assert sol.matrixSumQueries(
    3,
    [[0,0,1],[1,1,2]]
) == 9  # Mixed row and column updates

assert sol.matrixSumQueries(
    4,
    []
) == 0  # No queries

assert sol.matrixSumQueries(
    4,
    [[0,0,100000],[1,1,100000]]
) == 800000  # Large values

Test	Why
Example 1	Validates standard mixed operations
Example 2	Validates multiple overwrites
Single cell matrix	Smallest possible matrix
Later overwrite	Ensures newest assignment wins
Same row repeated	Tests skipping duplicate finalized rows
Same column repeated	Tests skipping duplicate finalized columns
Zero values	Ensures zeros handled correctly
Mixed operations	Validates row and column interaction
Empty query list	Ensures base case works
Large values	Validates large integer handling

Edge Cases

Repeated Updates to the Same Row

A common source of bugs is handling multiple updates to the same row.

For example:

[0,0,1]
[0,0,5]

The second query completely overwrites the first one.

When processing in reverse, the algorithm encounters 5 first and marks the row as visited. Later occurrences are ignored automatically.

This guarantees only the final assignment contributes to the answer.

Row and Column Overwrite Interactions

Another tricky case occurs when rows and columns overwrite each other.

Example:

[0,0,3]
[1,1,7]

The final matrix contains both operations interacting on overlapping cells.

The reverse-processing method handles this naturally by counting only still-unfixed rows or columns. Each cell is counted exactly once, preventing double counting.

Very Large Matrix Sizes

A naive implementation may attempt to allocate a 10000 x 10000 matrix.

That would require storing 10^8 cells, which is extremely memory intensive.

This implementation never constructs the matrix. Instead, it stores only two sets of visited rows and columns, keeping memory usage efficient even for the largest constraints.