JAVA | PriorityQueue | Simple
Intuition\n Describe your first thoughts on how to solve this problem. \n - Using an array to to track marked indices & Custom PriorityQueue ,we can mark ith in
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n - Using an array to to track marked indices & Custom PriorityQueue ,we can mark ith index and mark k minimum unmarked indices for all queries.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Need an array to to track marked indices\n- A data structure to store elements of nums array with respective indices ( we are gonna need index also to check if current element is already marked or not). A perfect data structure to implement this logic is PriorityQueue.\n- Custom pq where least element value will be at top and if value of both the elements is same then less index value will be at top\n- this way we can mark k unmarked elements\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogn)(for\xA0initialization)+O(m\u22C5(n+klogn))(for\xA0query\xA0processing)\n= O(m n log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```java []\nclass Solution {\n    public long[] unmarkedSumArray(int[] nums, int[][] queries) {\n        int n = nums.length;\n        int m = queries.length;\n        boolean[] isMarked = new boolean[n];\n        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> {\n            if (a.val != b.val) {\n                return a.val - b.val;\n            }\n            return a.idx - b.idx;\n        });\n\n        long totalSum = 0;\n        for (int i = 0; i < n; i++) {\n            totalSum += nums[i];\n            pq.add(new Pair(nums[i], i));\n        }\n\n        long[] ans = new long[m];\n        for (int i = 0; i < m; i++) {\n            int idx = queries[i][0];\n            int k = queries[i][1];\n            if (isMarked[idx] == false) {\n                isMarked[idx] = true;\n                totalSum -= nums[idx];\n            }\n            while (!pq.isEmpty() && k > 0) {\n                Pair temp = pq.poll();\n                if (isMarked[temp.idx] == false) {\n                    isMarked[temp.idx] = true;\n                    totalSum -= temp.val;\n                    k--;\n                }\n            }\n            ans[i] = totalSum;\n        }\n        return ans;\n    }\n}\n\nclass Pair {\n    int val;\n    int idx;\n\n    public Pair(int val, int idx) {\n        this.val = val;\n        this.idx = idx;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']