100% || Runtime: 100ms || Beats 100% users with java || Memory 66.65 MB
Intuition\nThis question is not based on logical thinking but is on implementation perspective.Every time we run a query we mark minimum value number in array a
# Intuition\nThis question is not based on logical thinking but is on implementation perspective.Every time we run a query we mark minimum value number in array and if the values are same then we mark number having minimul index. So the intuition is to use **Priority Queue (Min Heap)**. \n\n# Approach\nWe will use a visited array to track the unmarked array.You can use Set as well.Add Pair **{index,value}** in Priority Queue.\n`PriorityQueue<Pair> q = new PriorityQueue<>((a, b) -> {\n            if (a.val != b.val) {\n                return a.val - b.val;\n            }\n            return a.ind - b.ind;\n        });`\n\nEvery time we run a query we will check visited array. If it is not previously visited then we will visit and subtract its value from totalSum. \n\n*The idea of totalSum is we have to calculate the sum of unmarked elements after each querie so it is good to track marked elements sum and subtract it from totalSum to get answer.*\n\nNow for each querie we will mark `k` elements from the array having minimul value or index if needed.\n\n\n# Complexity\n- Time complexity:\n\n    **1**. Initializing Variables:\n    Initializing `n` with `queries.length` takes constant time, which is O(1).\n    Initializing `ans` with `new long[n]` takes O(n) time, where n is the length of queries.\n    Initializing vis with `new boolean[nums.length]` takes O(nums.length) time, which can be simplified to O(N), where N is the length of nums.\n    Initializing q with a `PriorityQueue` constructor takes O(m log m) time, where m is the size of nums.\n\n\n    **2**. First Loop (for summing up nums):\n    The loop iterates through nums once, so it takes O(N) time.\n\n    **3**. Second Loop (for processing queries):\n    The loop iterates through queries once, so it takes O(n) time, where n is the length of queries.\n    Inside this loop, there\'s a while loop with a PriorityQueue operation `(q.poll())`, which can take O(log m) time in each iteration, where m is the size of `nums`. In the worst case, this can happen for each query, so it can contribute O(n log m) time complexity.\n    Therefore, the overall time complexity of the given code can be expressed as:\n\n    O(1) + O(n) + O(N) + O(m log m) + O(n) + O(n log m)\n\n    **O(n log m)**, where `n` is the length of `queries` and `m` is the size of `nums`.\n\n- Space complexity:\n\n    **1**. `int n = queries.length;` and `long[] ans = new long[n];`: These statements use O(n) space where n is the length of queries.\n\n    **2**. boolean[] vis = new boolean[nums.length];: This array uses O(N) space where N is the length of nums.\n\n  **3**. `  PriorityQueue<Pair> q = new PriorityQueue<>((a, b) -> {...});:` The PriorityQueue q can contain up to m elements, where m is the size of nums. So, it can use O(m) space.\n\n    **4**. Variables inside the loops (int ind, int k, long sum, Pair temp, etc.) are constant space and don\'t contribute significantly to the overall space complexity.\n\n    Combining these, the total space complexity can be expressed as:\n\n    `O(n) + O(N) + O(m)`\n\n    In the worst case, if the sizes of queries and nums are both very large, the dominant term is O(m) due to the PriorityQueue q. However, since m is related to the size of nums, we can say that the space complexity is O(N) or O(m), where N is the length of nums\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    public static class Pair {\n        int val;\n        int ind;\n\n        public Pair(int val, int ind) {\n            this.val = val;\n            this.ind = ind;\n        }\n    }\n\n    public long[] unmarkedSumArray(int[] nums, int[][] queries) {\n        int n = queries.length;\n        long[] ans = new long[n];\n        boolean[] vis = new boolean[nums.length];\n        PriorityQueue<Pair> q = new PriorityQueue<>((a, b) -> {\n            if (a.val != b.val) {\n                return a.val - b.val;\n            }\n            return a.ind - b.ind;\n        });\n\n        long sum = 0; \n        for (int i = 0; i < nums.length; i++) {\n            sum += nums[i];\n            q.add(new Pair(nums[i], i));\n        }\n\n        for (int i = 0; i < n; i++) {\n            int ind = queries[i][0];\n            int k = queries[i][1];\n            if (!vis[ind]) {\n                vis[ind] = true;\n                sum -= nums[ind];\n            }\n\n            while (!q.isEmpty() && k > 0) {\n                Pair temp = q.poll();\n                if (!vis[temp.ind] && nums[temp.ind] > 0) {\n                    vis[temp.ind] = true;\n                    sum -= nums[temp.ind];\n                    k--;\n                }\n            }\n\n            ans[i] = sum < 0 ? 0 : sum;\n        }\n\n        return ans;\n    }\n}\n\n```
['Hash Table', 'Heap (Priority Queue)', 'Java']