Beats 100% - Heap and Set
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can use the heap data structure from collections to store the different elements (so
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can use the heap data structure from collections to store the different elements (sorted by val first then index).\n\nFor each query, we first check if index has already been marked (tracked with the removed set). Then we get the k smallest element (or stop if queue is empty, meaning everything was marked). We also checked that those kth smallest elements were not marked already.\n\nWe update our sum at each point and append it to our array\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: nlog(n)\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```swift []\n\nimport Collections\n\nstruct HE : Comparable {\n    var val : Int\n    var index : Int\n\n    static func < (l: HE, r: HE) -> Bool {\n        if l.val == r.val {\n            return l.index < r.index\n        }\n\n        return l.val < r.val\n\n\n    }\n}\n\nclass Solution {\n    func unmarkedSumArray(_ nums: [Int], _ queries: [[Int]]) -> [Int] {\n        var sum = 0 // keeps track of total sum\n        var q : Heap<HE> = []\n        \n        for (i, num) in nums.enumerated() { // build heap and total sum\n            sum += num\n            q.insert(HE(val: num, index: i))\n        }\n\n\n        var result : [Int] = [] // result array\n\n        var marked : Set<Int> = [] // keeps track of marked values (could also just modify array in place with -1)\n\n        for que in queries {\n            let index = que[0]; var k = que[1] \n            let num = nums[index]\n\n            if !marked.contains(index) { // if not marked, substract and mark\n                sum -= num\n                marked.insert(index)\n            }\n\n            \n            \n            while !q.isEmpty && k > 0 { // get k small elements\n                let e = q.popMin()!\n\n                if marked.contains(e.index) { // if marked ignore\n                    continue\n                }\n\n                marked.insert(e.index) // mark\n\n                sum -= e.val // substract from total\n                k -= 1 // decrease k\n            }\n\n            result.append(sum) // append result\n        }\n\n        return result\n    }\n}\n```
['Swift']