Java O(n) Solution with explanation | using Sets
Intuition\n Describe your first thoughts on how to solve this problem. \nLast query will always have all row/col filled. Starting from last query to 1st, each q
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLast query will always have all row/col filled. Starting from last query to 1st, each query will fill only those empty spaces left by pervious query.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n - Maintain a set each for rows and cols.\n - For each query starting from the last to first, check if the row/col to be filled is already filled. \n - If its already filled, that means in the natural order(first to last), the current value will get overwritten so no need to consider this query.\n - If not filled, add the row/col index to the row/col set respectively.\n - Check the size of col set for type == 0 and row set for type == 1. This will tell us number of columns/rows already filled. We will therefore have (n-size) cells which will be filled by current query. So increment in total sum from this query will be (n - size) * value(i.e. queries[i][2]) \n\n# Complexity\n- Time complexity: O(K), where K = length of queries array.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long matrixSumQueries(int n, int[][] queries) {\n        \n        Set<Integer> rows = new HashSet<>();\n        Set<Integer> cols = new HashSet<>();\n        \n        long sum = 0;\n        for(int i=queries.length-1; i>=0; i--) {\n            long currSum = 0;\n            if(queries[i][0] == 0) {\n                int row = queries[i][1];\n                if(rows.contains(row))\n                    continue;\n                rows.add(queries[i][1]);\n                int count = n - cols.size();\n                \n                currSum = (long) queries[i][2] * count;\n            } else {\n                int col = queries[i][1];\n                if(cols.contains(col))\n                    continue;\n                \n                cols.add(queries[i][1]);\n                int count = n - rows.size();\n                \n                currSum = (long) queries[i][2] * count;\n            }\n            \n            sum += currSum;\n        }\n        \n        return sum;\n    }\n}\n```
['Ordered Set', 'Java']