priority queue easy solution 100% submissionsss
\n\n Describe your first thoughts on how to solve this problem. \n\n# Intuition\n\nInitialize a priority queue (pq) to store pairs of values and their indices i
\n![1.png](https://assets.leetcode.com/users/images/3300534a-9b86-43cb-a6ba-5a354a2a974b_1710606551.0399086.png)\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Intuition\n\nInitialize a priority queue (pq) to store pairs of values and their indices in ascending order based on the value. This allows us to efficiently identify and remove the smallest elements.\nIterate through the queries vector. For each query:\nRemove the queried element from the running sum totalsum and mark it as visited in the mp unordered map.\nWhile there are remaining removals (k > 0) and the priority queue is not empty:\nRemove elements from the priority queue until an unvisited element is encountered, decrementing k with each removal.\nUpdate the answer array with the current totalsum.\nReturn the answer array.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nInitializing the priority queue: O(n * log(n)), where n is the size of the nums vector.\nIterating through the queries vector: O(q), where q is the number of queries.\nWithin each query iteration, the while loop may potentially pop elements from the priority queue. In the worst case, it may pop all elements, which would be O(n * log(n)). However, each element can only be popped once, so across all queries, this operation would be O(n * log(n)) in total.\nOverall time complexity: O((n + q) * log(n)), where n is the size of nums and q is the number of queries.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nPriority Queue (pq): O(n), as it can store up to all elements of nums.\nAnswer array (ans): O(q), where q is the number of queries.\nOther variables and data structures: O(n).\nOverall space complexity: O(n + q).\n\n\n\n\ni submitted it after test in test i made some small mistakes due to which got tlepr\n\n# Code\n```\nclass Solution {\npublic:\n    vector<long long> unmarkedSumArray(vector<int>& nums, vector<vector<int>>& queries) {\n      \n        \n//         vector<long long> ans;\n//         unordered_map<int,bool> mp;\n//         int n=nums.size();\n       \n//         for(auto it:queries){\n           \n//             int index=it[0];\n//             int k=it[1];\n//             if(!mp[index]){\n//                 mp[index]=true;\n//             }\n//             priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n//             for(int i=0;i<n;i++){\n//                 if(!mp[i]){\n//                     pq.push({nums[i],i});\n//                 }\n//             }\n//             while(k>0 && !pq.empty()){\n//                 auto[val,ind]=pq.top();\n//                 pq.pop();\n//                 if(!mp[ind]){\n//                     mp[ind]=true;\n//                     k--;\n//                 }\n//             }\n            \n//             long long sum=0;\n//             for(int i=0;i<n;i++){\n//                 if(!mp[i]){\n//                     sum+=nums[i];\n//                 }\n//             }\n//             ans.push_back(sum);\n            \n            \n            \n            \n//         }\n//         return ans;\n//         int n=nums.size();\n//         unordered_map<int,int> mp;\n//         vector<long long> ans;\n//         priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        \n//         for(int i=0;i<n;i++){\n//             pq.push({nums[i],i});\n            \n//         }\n        \n//         for(auto it:queries){\n//             int ind=it[0];\n//             int k=it[1];\n            \n//             if(!mp[ind]){\n//                 mp[ind]=true;\n//             }\n//             while(k>0 && !pq.empty()){\n//                 auto[val,idx]=pq.top();\n//                 pq.pop();\n//                 if(!mp[idx]){\n//                     mp[idx]=true;\n//                     k--;\n//                 }\n//             }\n            \n//             long long sum=0;\n//             for(int i=0;i<n;i++){\n//                 if(!mp[i]){\n//                     sum+=nums[i];\n                    \n//                 }\n//             }\n//             ans.push_back(sum);\n//         }\n//         return ans;\n\n        int n=nums.size();\n        unordered_map<int,int> mp;\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        vector<long long> ans(queries.size());\n        long long totalsum=0;\n        for(int i=0;i<n;i++){\n            pq.push({nums[i],i});\n            totalsum+=nums[i];\n            \n            \n        }\n        int l=0;\n        \n        for(auto it:queries){\n            int ind=it[0];\n            int k=it[1];\n            if(!mp[ind]){\n                mp[ind]=true;\n                totalsum-=nums[ind];\n                \n            }\n            while(k>0 && !pq.empty()){\n                auto[val,idx]=pq.top();\n                pq.pop();\n                if(!mp[idx]){\n                    mp[idx]=true;\n                    totalsum-=nums[idx];\n                    k--;\n                }\n            }\n            \n            ans[l]=totalsum;\n            l++;\n        }\n        return ans;\n        \n        \n        \n        \n\n    }\n};\n```
['Ordered Map', 'Heap (Priority Queue)', 'C++']