Leetcode 2718: Sum of Matrix After Queries
You are given a number n and a list of queries. Initially, an n x n matrix is filled with zeros. Each query updates either a row or a column in the matrix to a given value. After applying all the queries, compute and return the sum of all elements in the matrix.
Problem
Approach
Steps
Complexity
Input: A number n and a list of queries, where each query is of the form [typei, indexi, vali].
Example: n = 3, queries = [[0, 0, 1], [1, 2, 2], [0, 2, 3], [1, 0, 4]]
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
Output: Return the sum of all elements in the matrix after all queries are applied.
Example: 23
Constraints:
• The sum will be a non-negative integer.
Goal: The goal is to efficiently calculate the sum of the matrix after applying all queries.
Steps:
• Keep track of the changes for each row and column separately.
• Process the queries in reverse order to minimize redundant updates.
• Update the matrix based on the query type (row or column) and compute the sum.
Goal: The input constraints ensure the solution must handle large matrices efficiently.
Steps:
• 1 <= n <= 10^4
• 1 <= queries.length <= 5 * 10^4
• 0 <= vali <= 10^5
Assumptions:
• The matrix is initially filled with zeros.
• Input: Example 1
• Explanation: For n = 3 and queries = [[0, 0, 1], [1, 2, 2], [0, 2, 3], [1, 0, 4]], we update the matrix according to the queries and calculate the sum of all elements.
• Input: Example 2
• Explanation: For n = 3 and queries = [[0, 0, 4], [0, 1, 2], [1, 0, 1], [0, 2, 3], [1, 2, 1]], the sum of all matrix elements after applying the queries is 17.
Approach: The approach involves processing the queries in reverse order to optimize the number of updates, while keeping track of the sum of all matrix elements.
Observations:
• The matrix can be updated by rows or columns, so we need to handle each query based on its type.
• We can use a greedy approach by iterating through the queries in reverse to minimize redundant operations and compute the final sum.
Steps:
• Initialize an empty matrix with zeros.
• Iterate through the queries in reverse order, applying each one and updating the sum.
• Handle row and column updates separately and adjust the sum accordingly.
Empty Inputs:
• There are no empty inputs since queries length is guaranteed to be at least 1.
Large Inputs:
• Handle large matrix sizes and a high number of queries efficiently using an optimized approach.
Special Values:
• If the matrix size is 1, the result is directly the value of the first query.
Constraints:
• The solution must handle up to 10^4 matrix size and 5 * 10^4 queries efficiently.
long long matrixSumQueries(int n, vector<vector<int>>& q) {
long long res = 0;
int seen[2][10001] = {};
int cnt[2] = {n, n};
for(int i = q.size() - 1; i >= 0; i--) {
int type = q[i][0], id = q[i][1], val = q[i][2];
if(!seen[type][id]) {
seen[type][id] = 1;
res += val * cnt[!type];
--cnt[type];
}
}
return res;
}
1 : Function Definition
long long matrixSumQueries(int n, vector<vector<int>>& q) {
The function `matrixSumQueries` is defined, accepting an integer `n` (the size of the matrix) and a 2D vector `q` containing the queries. It returns a long long integer representing the calculated sum after processing all queries.
2 : Variable Initialization
long long res = 0;
The variable `res` is initialized to 0, which will hold the cumulative result of all valid queries.
3 : Array Initialization
int seen[2][10001] = {};
The `seen` array is initialized to track whether a particular row or column has been processed. It has dimensions 2 by 10001 to accommodate the two types of queries and matrix indices.
4 : Array Initialization
int cnt[2] = {n, n};
The `cnt` array is initialized with `n` for both rows and columns, representing the number of rows and columns available for modification.
5 : Loop Start
for(int i = q.size() - 1; i >= 0; i--) {
A loop is initiated that iterates through the queries in reverse order, starting from the last query and moving backward to the first.
6 : Query Parsing
int type = q[i][0], id = q[i][1], val = q[i][2];
For each query, the variables `type`, `id`, and `val` are extracted. `type` specifies whether the operation is on a row or a column, `id` is the row or column index, and `val` is the value to be added to the matrix.
7 : Condition Check
if(!seen[type][id]) {
The condition checks if the row or column has already been processed in a previous query. If not, it proceeds with the operation.
8 : Mark As Seen
seen[type][id] = 1;
The element at the specified type and index (`type`, `id`) is marked as processed by setting `seen[type][id]` to 1.
9 : Result Calculation
res += val * cnt[!type];
The result is updated by adding the value of the query (`val`) multiplied by the remaining count of rows or columns that have not yet been processed (`cnt[!type]`).
10 : Decrement Count
--cnt[type];
The count for the type (row or column) is decremented, as one row or column has now been processed.
11 : Return Result
return res;
The final result is returned, which is the sum of all valid query contributions.
Best Case: O(n + m)
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The time complexity is linear in terms of the number of queries and matrix size.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) since we only store a few arrays to track row and column updates.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus