Easy-to-understand sorting solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nSo, for this problem all we need to do is to keep track of the sum of the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nSo, for this problem all we need to do is to keep track of the sum of the array after every query, which can be broken down into two parts: \n\n1. Subtracting the ith array value from the sum if it hasn\'t already been subtracted, which is trivial.\n2. Subtracting k smallest unmarked array elements\' values from the sum; if the value is marked we just keep iterating until we find an unmarked element, or all elements are marked (k unmarked elements must be found per query).\n\nSo, there is a few problems that will be ran into:\n\n1. How can we mark elements, near-optimally?\n\n   - We can mark elements by putting their respective indexes into a set; and so to see if an element is marked or not, we will just check if its index is in the set.\n\n2. How can we find kth smallest unmarked elements, near-optimally?\n    - We can make a seperate array of tuples where each tuple has two elements: value and index; so we will iterate through the input array, and for each value, we will make a tuple with both it, and its index.\n    - From there we can use a custom sorting algorithm that sorts by value first, and then if there are two equal values, by index. We sort this in reverse order and so what is left is an array of tuples where the smallest values are at the last index.\n    - So, at this point, we can find the kth smallest value, but since they can be marked, there might be a lot of sidestepping to find an umarked one; this is why we sorted in reverse order: we can just delete the -1th tuple in o(1) time as its marked, which results in the smallest unmarked values constantly appearing at the end of the array.\n\n3. How can we check if all values are marked, near-optimally?\n    - Since all marked values will be deleted as they are marked or appear at the end of the array, the array will eventually be empty if the queries force it to be, which we can just break from the loop at that point.\n    - If the queries don\'t mark all values and thus empty the tuple array, then the loops will simply stop when the queries do.\n\n\n\n\n# Complexity\n- Time complexity:\nO(n log n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n        check = set()               # check for marked values\n        s = sum(nums)\n        smallest = [(n,i) for i,n in enumerate(nums)]\n        smallest.sort(key = lambda x: (x[0], x[1]), reverse=True)\n                                    # array of (val, idx) tuples\n        ans = [] \n\n        for idx, small in queries:\n            if idx not in check:    # mark unmarked values\n                check.add(idx)\n                s -= nums[idx]      # update sum\n            for i in range(small):\n                while len(smallest) and smallest[-1][1] in check:\n                    del smallest[-1]# delete marked values\n                if not smallest:    \n                    break           # mark unmarked values\n                check.add(smallest[-1][1])\n                s -= smallest[-1][0]\n\n            ans.append(s)           # append updated sum at query end\n        return ans\n                    \n            \n        \n```
['Hash Table', 'Sorting', 'Python3']