PriorityQueue (minHeap) No Sorting Java
So there are a couple ways this problem can be solved. TreeMap, Sorting indices or a PriorityQueue. I prefer a minHeap PriorityQueue as we can easily use a cust
So there are a couple ways this problem can be solved. TreeMap, Sorting indices or a PriorityQueue. I prefer a minHeap PriorityQueue as we can easily use a custom comparator (or directly a lamba function) to offer elements in sorted order as per our liking (Smallest elements with smaller indices on top!). Lastly, all we need is a `boolean[] visited` to keep track of the marked elements. We can also use a HashSet/HashMap for this, but boolean[] saves a lot of overhead!\nFinally before the code, a wonderful trick I used is to sum up all elements of nums beforehand, and then subtract an unmarked "idx OR one of the K" elements for each query! Its the same as going through entire array and all up all unmarked elements, we do in reverse, sum the total and subtract marked ones!\nI encourage to go through this code. We basically simulate what the problem asks for each query!\n```\nclass Solution {\n    public long[] unmarkedSumArray(int[] nums, int[][] queries) {\n        int n = nums.length, m = queries.length;\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] \n        ? a[0] - b[0] : a[1] - b[1]);\n        long sum = 0;\n        for (int i = 0; i < n; i++) {\n            sum += nums[i];\n            pq.offer(new int[]{nums[i], i});\n        }\n        boolean[] visited = new boolean[n];\n        long[] res = new long[m];\n        for (int i = 0; i < m; i++) {\n            int idx = queries[i][0], k = queries[i][1];\n            if (!visited[idx]) {\n                visited[idx] = true;\n                sum -= nums[idx];\n            }\n            while (!pq.isEmpty() && k > 0) {\n                int[] item = pq.poll();\n                if (!visited[item[1]]) {\n                    visited[item[1]] = true;\n                    sum -= item[0];\n                    k--;\n                }\n            }\n            res[i] = sum;\n        }\n        return res;\n    }\n}\n```\n\nSo, there are 2 main things to notice in my solution\n1. We only subtract when there is an unvisited element. For each query, we have to **mark** the element at index `queries[i][0]` and Also we have to **mark** the **k smallest unmarked** elements where `k = queries[i][1]`. Therefore, in our attempt to find such elements for either of these 2 cases, we must choose only `unvisited` ones and make sure to `visit` them by setting those indices to `true`\n2. Probably the most tricky part. For each query when we are trying to find the **k smallest unmarked** elements, we are polling elements from the minHeap. But, we must ONLY **choose** a polled item IF it is `unmarked`! If it was already visited (meaning marked by another queries type 1 marking), we can\'t choose it. We choose an element by decrementing k until `k > 0 && minHeap not empty`. This takes care of the case when there are less than "k" elements in our heap as we make sure not to poll from empty heap\n\nEasy
['Java']