[C++] ✅ Straight-forward O(n) Solution w/ Intuition + Code [Traversing Queries from End]
Intuition\nWe can think of this problem as painting a grid wall. At every query, you\'re painting the q[i][1]^{th} row/columns based on type, with paint q[i][2]
# Intuition\nWe can think of this problem as painting a grid wall. At every query, you\'re painting the $$q[i][1]^{th}$$ row/columns based on type, with paint $$q[i][2]$$.\nNow a simple thing that you need to think of is that when the if a part of wall is painted with color `x` and later on if that part is painted with paint `y` then the color `y` will be the current color of the wall which in this case is the value of the cell.\n\nThis means that we can traverse the queries from the end and add the `val` for the respective row/columns, and if the same row/column is being painted in an earlier query we can ignore the change.\n\nAnother important thing is to know is that if we\'re painting a row and if two columns of that row are painted in a later query, we need to ignore those two columns\' values. We\'ll decrease the number of columns when we paint rows and vice versa. This will be more clearer in the approach and the code.\nSimilar to the above point, we need to take care of the same row/column being painted twice. Only the latest query for that row should be considered. (we\'ll use a HashSet for this)\n\n# Approach\n1. Store the number of rows `r` and columns `c`\n2. Create two vectors (one for Rows Filled and one for Columns Filled) to see if the row/columns is already filled at a later point.\n3. Repeat step `4` to `x` for all queries from **end** to **start**\n4. If `type == 0` and `row is not painted` then add `c*val` to the answer. Reduce `r` by `1`. Mark row as painted.\n5. If `type == 1` and `column is not painted` then add `r*val` to the answer. Reduce `c` by `1`. Mark columns as painted.\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        int r=n, c=n;\n        vector<bool> rf(n, false), cf(n, false);\n        long long res{0ll};\n        for(int i=queries.size()-1; i>=0 && r>=0 && c>=0; i--) {\n            int type = queries[i][0];\n            int idx = queries[i][1];\n            int val = queries[i][2];\n            if (type == 0) {\n                if (rf[idx]) continue;\n                res += (long long)c*val;\n                r--;\n                rf[idx] = true;\n            }\n            else {\n                if (cf[idx]) continue;\n                res += (long long)r*val;\n                c--;\n                cf[idx] = true;\n            }\n        }\n        \n        return res;\n    }\n};\n```\n\n# Complexity\n- Time complexity: $$O(||queries||)$$\nSince we\'re traversing through all the queries, it\'ll take the number of queries time.\n\n- Space complexity: $$O(n + n)$$\nSince we\'re using two Arrays/HashSets.\n\n\n> ### Note\n> - Upvote if you liked my solution\n> - Drop a comment if you have any doubt
['Hash Table', 'Matrix', 'C++']