[C++] Prefix Sum + Min-Heap + Bool Array to Mark Indexes, 100% Time (189ms), 100% Time (127.94MB)
This problem requires us to both remove specific indexes and fixed amounts of smaller ones: that should suggest us we need two different sets of data structures
This problem requires us to both remove specific indexes and fixed amounts of smaller ones: that should suggest us we need two different sets of data structures pieces of logic to make it work, plus some extra logic to wield all the cogs in an unified mechanism.\n\nFor the first requirement (removing specific indexes) we will use a boolean array, the cheapest option to do this kind of work when we have a limited range (in our case, all the indexes in the `[0, n)` interval).\n\nFor the second requirement, we will be using a min-heap of values and indexes.\n\nWith that in mind, the only thing left is to compute the result and we can do so by computing the initial sum and then reducing it by every newly marked element, to avoid us the pain of recomputing the sum of each remaining element at each step.\n\nWe will declare `pqType` as `pair<int, int>` and then all our support variables:\n* `pq` is going to be our min-heap;\n* `nLen` and `qLen` will store the length of `nums` and `queries`, respectively;\n* `w` will be our writing pointer when populating `res`;\n* `k`, `n` and `idx` all support variables we will use in our main loop;\n* `sum` will store the current sum of all the unmarked elements - initially set to be the sum of each single element in `nums`;\n* `marked` is the boolean array we will use to keep track of all the marked elements;\n* `res` will be our usual result variable, initially set to be `qLen`-sized to avoid expensive and unnecessary reallocations as we compute our result.\n\nAfter feeling all the cells in `marked` with `false` and `pq` with all the elements from `nums` paired with their original index, we can start taking each `query` in `queries` and with it we will:\n* store `query[0]`, the index to be marked, in `idx`;\n* store `query[1]`, the amount of smaller values to be removed, in `k`;\n* if `idx` was not marked before (ie: `marked[idx] == false`), we will:\n    * subtract `nums[idx]` from `sum`;\n    * flag `idx` as marked;\n* remove the `k` smallest elements, is possible, by looping `while` either `k > 0` or `pq` is not empty and we will:\n    * extract `n` and `idx` from the element on top of `pq` (ie: the one with the smallest value and index);\n    * `pop` it out of `pq`;\n    * if `idx` was already marked, we will just `continue`;\n    * otherwise, similarly to above we will reudce `sum` by `n` and flag `idx` as marked;\n    * decrease `k` by `1`;\n* write `sum` in res[w]`;\n* advance `w` by one position.\n\nOnce done, we can finally `return` `res` :)\n\n# Complexity\n- Time complexity: $$O(n * log(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nusing pqType = pair<int, int>;\n\nclass Solution {\npublic:\n    vector<long long> unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries) {\n        // support variables\n        priority_queue<pqType, vector<pqType>, greater<pqType>> pq;\n        int nLen = nums.size(), qLen = queries.size(), w = 0, k;\n        long long sum = accumulate(begin(nums), end(nums), 0ll), n, idx;\n        bool marked[nLen];\n        vector<long long> res(qLen);\n        // preparing marked\n        memset(marked, 0, nLen * sizeof(bool));\n        // populating pq\n        for (int i = 0; i < nLen; i++) {\n            pq.push({nums[i], i});\n        }\n        // parsing queries\n        for (auto &query: queries) {\n            // getting the first n\n            idx = query[0], k = query[1];\n            // marking and removing n if we did not so before\n            if (!marked[idx]) {\n                sum -= nums[idx];\n                marked[idx] = true;\n            }\n            // removing the next k smallest values\n            while (k && pq.size()) {\n                auto [n, idx] = pq.top();\n                pq.pop();\n                // ignoring premarked values\n                if (marked[idx]) continue;\n                sum -= n;\n                marked[idx] = true;\n                k--;\n            }\n            res[w++] = sum;\n        }\n        return res;\n    }\n};\n```\nWe can improve performance slightly more if we realise that once we have remove all the elements, there is no point in even considering any new queries, so we can change the last lines of our main loop like this:\n\n```cpp\n        /* ... */\n            // stopping parsing if we already marked all the elements\n            if (!sum) return res;\n            // writing the current value of sum in res otherwise\n            res[w++] = sum;\n        /* ... */\n```\n\n# Brag\n![image.png](https://assets.leetcode.com/users/images/6ed2a764-66e9-4424-be14-c697f74acc8a_1710664811.1922085.png)\n
['Array', 'Heap (Priority Queue)', 'Prefix Sum', 'C++']