[C++, Java, Python] Track Seen Count | With Image Example
Intuition\n\nn = 10, queries = [[1, 7, 1], [0, 6, 2]]\n\n\n\nThe queries which will come later will have a greater impact on final sum because it will overwrite
# Intuition\n```\nn = 10, queries = [[1, 7, 1], [0, 6, 2]]\n```\n![image.png](https://assets.leetcode.com/users/images/f398ef4c-142a-4692-9c06-282f8e3728d2_1685851113.5247235.png)\n\nThe queries which will come later will have a **greater** impact on final sum because it will overwrite any cell that was filled/not-filled before. Therefore, we can try to make sum by traversing in reverse direction of `queries`.\n\nIn above example,\n1. We can first add `2 * 10 = 20` to our sum because it will overwrite everything as it is the **last** query.\n2. Then, while considering the previous query `[1, 7, 1]`, we need to know how many rows will be there that would have been overwritten in upcoming queries. So, we can track this by maintaining seen rows\' count. By this we will know that there is one row that will be overwritten in future so we add `1 * 9 = 9` to our sum.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        int rowSeenCount = 0, colSeenCount = 0;\n        vector<bool> rowSeen(n), colSeen(n);\n        long long sum = 0;\n        for (int qi = queries.size() - 1; qi >= 0; qi--) {\n            int type = queries[qi][0], index = queries[qi][1], val = queries[qi][2];\n            if (type == 0 && !rowSeen[index]) {\n                rowSeenCount++;\n                rowSeen[index] = true;\n                sum += 1LL * (n - colSeenCount) * val;\n            }\n            if (type == 1 && !colSeen[index]) {\n                colSeenCount++;\n                colSeen[index] = true;\n                sum += 1LL * (n - rowSeenCount) * val;\n            }\n        }\n        return sum;\n    }\n};\n```\n```Java []\nclass Solution {\n    public long matrixSumQueries(int n, int[][] queries) {\n        int rowSeenCount = 0, colSeenCount = 0;\n        boolean[] rowSeen = new boolean[n];\n        boolean[] colSeen = new boolean[n];\n        long sum = 0;\n        for (int qi = queries.length - 1; qi >= 0; qi--) {\n            int type = queries[qi][0], index = queries[qi][1], val = queries[qi][2];\n            if (type == 0 && !rowSeen[index]) {\n                rowSeenCount++;\n                rowSeen[index] = true;\n                sum += (n - colSeenCount) * val;\n            }\n            if (type == 1 && !colSeen[index]) {\n                colSeenCount++;\n                colSeen[index] = true;\n                sum += (n - rowSeenCount) * val;\n            }\n        }\n        return sum;\n    }\n}\n```\n```Python []\nclass Solution:\n    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n        rowSeenCount, colSeenCount, total = 0, 0, 0\n        rowSeen, colSeen = [False] * n, [False] * n\n        for qi in range(len(queries) - 1, -1, -1):\n            typei, index, val = queries[qi][0], queries[qi][1], queries[qi][2]\n            if typei == 0 and not rowSeen[index]:\n                rowSeenCount += 1\n                rowSeen[index] = True\n                total += (n - colSeenCount) * val\n            if typei == 1 and not colSeen[index]:\n                colSeenCount += 1\n                colSeen[index] = True\n                total += (n - rowSeenCount) * val\n        return total\n```\n\n# Complexity\n- Time complexity: $$O(queries.length)$$\n- Space complexity: $$O(n)$$\n\n# QnA\n**Q:** [@Bacon_lord](/Bacon_lord) : I dont understand why we need to track the rows/cols, shouldn\'t counting the rows/cols be enough, and once you reach n no need to increment further.... this is wrong but i dont understand why it\'s wrong?\n**A:** It is required as there can be multiple queries for same row (or same column). Take same example as above, add another query: \n```\nn = 10, queries = [[1, 7, 1], [0, 6, 3], [0, 6, 2]]\n```\nFinal matrix will be same as in above image. But if we counted same row `6` twice, then when we reach `[1, 7, 1]` we will do `1 * 8 = 8` but we should have done `1 * 9 = 9`.\nAlso, those multiple queries are meaningless because only last of all the same will be in the final result as it will overwrite on completely same row (or column). Since we are traversing in reverse direction, we put it in hashmap or visited array and we will not consider queries to same row (or column) that would have been made in past with respect to it.
['Hash Table', 'C++', 'Java', 'Python3']