Reveres Query Order | Clean Intuition | Beginner Friendly | Well Explained
Intuition\nThe simple brute-force solution would be to update each row and each column and then update the sum accordingly as we iterate through the queries. Ti
# Intuition\nThe simple brute-force solution would be to update each row and each column and then update the sum accordingly as we iterate through the queries. Time complexity of that would be $O(n * q)$ where $n$ is the length of matrix and $q$ is the number of queries. It is valid but non optimal because except for some very special cases you woud have to udpate the same cell many times. \n\nCan it be improved then?\n**YES!** \n\nIn this problem we have to give what the sum will be at the END of all the queries. \n\nNotice that if we have to operations which changes the same row, then the first one will be discarded after the second. The same goes for doing two operations on columns. So it seems to be a good idea to work on that problem by looking at the queries from the end so just reverse the queries array. Then if we see an operation on the row we have already proceeded we skip it - instead of doing $O(n)$ operations as in the brute-force solution. The same goes for columns. So for every new/row column we will have to add $n * newVal$ to our result, right?\nNot quite - let\'s say we have already proceeded $k$ rows then if have to update new column for the first time it will add to our result only $(n - k) * newVal$ because those $k$ values would be covered up by the $k$ rows that are after - in the original order - we have already proceeded. \nAnalogically for the rows - if we see new row and we have already coverd $j$ columns we increase our result only by $(n - j) * newVal$.\n\n# Approach\nFrom the intuition we have to keep track of:\n- which rows are covered - `rows`,\n- which columns are covered - `columns`\n\nwe will use boolean array for that, and:\n- how many rows are covered - `rows_covered`,\n- how many columns are covered - `columns_covered`\n\nthis can be done by simple counter.\n\nThen reverse the `queries` array and for each `query` if it is an operation on row we:\n- check if this row is already covered and if so - go to the next query\n- if not update the answer by `(n - columns_coverd) * newVal` where `newVal` is the value of the query\n- increase the numbers of `rows_covered` by one\n- mark that this row has been checked\n\nThere is completely symetrical analogy for when we have to change the valus of column instead of row. \n<!-- Describe your approach to solving the problem. -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        long long ans = 0;\n        vector<bool> rows(n), columns(n);\n        int rows_covered = 0, columns_covered = 0;\n        for (int i = queries.size() - 1; i >= 0; --i) {\n            vector<int> v = queries[i];\n            if (v[0] == 0) {\n                if (rows[v[1]])\n                    continue;\n                ans += (n - columns_covered) * v[2];\n                ++rows_covered;\n                rows[v[1]] = true;\n            }\n            if (v[0] == 1) {\n                if (columns[v[1]])\n                    continue;\n                ans += (n - rows_covered) * v[2];\n                ++columns_covered;\n                columns[v[1]] = true;\n            }\n            if (rows_covered == n && columns_covered == n)\n                break;\n        }\n        return ans;\n    }\n};\n```\n\n# Complexity\n- Time complexity: $O(q)$ where $q$ is the number of queries because for each query we do constant number of operations (check if covered, increase sum, increase the number of covered rows/columns, mark the row/column as covered).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$ where $n$ is the number of rows/columns to keep track of proceeded rows/columns.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Array', 'Math', 'C++']