Explained with short examples || O(Q) || C++
Intuition and Appraoch\nIt doesnt make sense to process the queries from the start.\nBecause some query from the future can replace this query that can change t
# Intuition and Appraoch\nIt doesnt make sense to process the queries from the start.\nBecause some query from the future can replace this query that can change the answer.\n\n***So its better to process queries from the end***\n\nAnd we dont need to process pair duplicate queries(For ex: 0 operation on row 5 once happened, cant happen again, as we are traversing backwards)\nStore the first two part of the queries in set or hashset to check for this condition.\n\n***Any row operation reduces the cells in the columns which contribute to the sum and any column operation reduces the cells in rows that contribute to the sum(this was the main operation)***\n\nFor ex: Once we replace all values of row 4, as we are processing queries form the end, doesnt matter what queries are, this row will remain unchanged.\nIt is the same as reducing a cell form every column of the matrix.\nSame goes for column operation and row cells.\n\n[ Read example again and think, if not able to understand, its like layers ]\n\nSo maintaing a rowCellCount and colCellCount will be helpful to make the answer.\n\nif (type == 0){\n\t\tcolCells--;\n\t\tans += rowCells * val;\n}\nelse{\n\t\trowCells--;\n\t\tans += colCells * val;\n}\n\n\n# Complexity\n- Time complexity:\nO(queries.size)\n\n- Space complexity:\nO(n)\n\n# Code\n```\n\ntypedef long long ll;\nclass Solution {\npublic:\n\tlong long matrixSumQueries(int n, vector<vector<int>>& queries) {\n\t\tlong long ans = 0;\n\t\tll rowCells = n;\n\t\tll colCells = n;\n\t\tunordered_set<int> st;\n\t\tll type, index, val;\n\t\tint key;\n\t\tfor (int i = queries.size() - 1; i >= 0 ; --i)\n\t\t{\n\t\t\ttype = queries[i][0];\n\t\t\tindex = queries[i][1];\n\t\t\tval = queries[i][2];\n\t\t\tkey = type==0? 0 : n;\n\t\t\tkey += index;\n\t\t\tif (st.find(key) != end(st))\n\t\t\t\tcontinue;\n\t\t\tst.insert(key);\n\t\t\tif (type == 0)\n\t\t\t{\n\t\t\t\tcolCells--;\n\t\t\t\tans += rowCells * val;\n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\trowCells--;\n\t\t\t\tans += colCells * val;\n\t\t\t}\n\t\t}\n\t\treturn ans;\n\t}\n};\n\n\n```\n\nUpvote if you found this helpful!
['C++']