REAL HARD✅ || 3 Methods || Explained✅
<<<<UPvote\n\n\n\nIDEA\nThe brute force requires every cell to be traversed so it will cause TLE (n^2).\nSince the order of queries also matters, so we can\'t s
**<<<<UPvote**\n\n\n\n**IDEA**\nThe brute force requires every cell to be traversed so it will cause TLE (n^2).\nSince the order of queries also matters, so we can\'t simply store the change and result them all later.\n**1st Approach**\nIn this approach, we iterate from the end and keep track of remaining rows and columns. We calculate the contribution based on the current value and remaining rows/columns, considering the effect of row and column operations. By decrementing the counts for each operation, we ensure accurate calculation of the contribution.\n\n```\nlong long matrixSumQueries(int n, vector<vector<int>>& q) {\n        vector<bool> rowFlag(n, 1), colFlag(n, 1);\n        long long ans = 0, rowRemain = n, colRemain = n;\n        for(int i = q.size()-1; i >= 0; --i){\n            if(q[i][0] == 0 && rowFlag[q[i][1]]) { ans += colRemain * q[i][2];    rowFlag[q[i][1]] = 0; rowRemain--; }\n            if(q[i][0] == 1 && colFlag[q[i][1]]) { ans += rowRemain * q[i][2];    colFlag[q[i][1]] = 0; colRemain--; }\n        }\n        return ans;\n    }\n\n```\n\n\n\n**2nd Approach**\n\nWe start with the last query and go backwards.\n\nWe track if we have seen a row or column with id - so we can ignore earlier queries that will be overwritten.\n\nWe also count how many rows and columns have not been seen in cnt.\n\nThis way, each query adds v * cnt, where cnt is the count of unseen rows (for type == 0) or columns (for type == 1).\n\n```\nlong long matrixSumQueries(int n, vector<vector<int>>& qs) {\n    long long res = 0, cnt[2] = {n, n};\n    bool seen[2][10001] = {};\n    for (int i = qs.size() - 1; i >= 0; --i) {\n        int type = qs[i][0], id = qs[i][1], v = qs[i][2];\n        if (!seen[type][id]) {\n            seen[type][id] = true;\n            res += v * cnt[!type];\n            --cnt[type];\n        }\n    }\n    return res;\n}\n```\n\n**3rd Approach**\n\n\nSuppose if a cell is made under two or more updations, then the final value will surely update the previous and it will be the answer. So if we approach from backwards (in the queries array) and then check if the current cell is already updated then it means we don\'t need to sum the current value.\n\n**Complexity**\nTime complexity:\nO(queries.length())\nSpace complexity:\nO(n)\nCode\n```\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        \n        vector<int> rowV(n, -1), colV(n, -1);\n        int rowC, colC;\n        \n        //It is done only to make the backward iteration simpler.\n        reverse(queries.begin(), queries.end());\n        \n        long long sum=0;\n        for(auto q : queries) {\n            if((q[0] == 0 && rowV[q[1]] != -1) || (q[0] == 1 && colV[q[1]] != -1)) {\n                continue;        \n            }\n            else {\n                if(q[0] == 0) {\n                    sum += (n-colC)*q[2];\n                    rowV[q[1]] = q[2];\n                    rowC++;\n                }\n                else {\n                    sum += (n-rowC)*q[2];\n                    colV[q[1]] = q[2];\n                    colC++;\n                }\n                \n            }\n        }\n        \n        return sum;\n    }\n};\n```\n\n\n
['C']