O(E*Log K) | Why to use minHeaps and not maxHeaps to get most optimized time | 2 solutions | C++
TYPE 1 - SORT it and use it . SIMPLE\n# Intuition\n Describe your first thoughts on how to solve this problem. \n- Its actually so simple.\n- We make adj list w
# TYPE 1 - SORT it and use it . SIMPLE\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Its actually so simple.\n- We make adj list with NOde and its value\n- We need to find star sum for all nodes one by one\n- Star sum is nothing but sum of ur val + ur adj nodes vals (at max u can select k adj nodes = k edges) (0 to k possible selections)\n- Where to stop selection. The first negative guy is the answer. As neg val reduces the sum. we need max sum.\n- sort it in DESC ORDER so that u know the stop point. first neg u can stop. As after 1st neg, rest also neg only.\n\n\n\n# Complexity\n- Time complexity: O(E) + O(N^2 LOG N) + O(N) + O(N^2) = O(N^2 Log N) Dominating term\n- Say ur graph is complete graph\n- so node has N-1 edges so those many adj[] list len\n- so it takes O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(V+E) adj list\n- \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {\n        int N = vals.size();\n        int M = edges.size();\n        \n        vector<pair<int,int>> adj[N];\n        \n        for(auto e : edges){\n\n            adj[e[0]].push_back({vals[e[1]],e[1]});\n            adj[e[1]].push_back({vals[e[0]],e[0]});\n            \n        }\n\n        for(int i=0; i<N; i++){\n            sort(adj[i].begin(), adj[i].end(), greater<pair<int,int>>());\n        }\n\n        int maxSum = INT_MIN;\n\n        for(int i=0; i<N; i++){\n            int sum = vals[i];\n            int j = 0;\n            for(auto it : adj[i]){\n                if(it.first<0 || j>=k){\n                    break;\n                }\n                \n                sum += it.first;\n                j++;\n            }\n            \n            maxSum = max(sum, maxSum);\n        }\n        \n        return maxSum;\n        \n    }\n};\n```\n\n# Type 2 - bit Complex - minHeaps used.\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- See its same as above. find star sum for every node and give the max.\n- The point over hear is that we use minheap to find top K max elements.\n- MinHeap character : O(1) to find min. O(log K) delete and insert ops.\n- we never allow size of heap to grow more than k. This is the TURNING POINT.\n- So that always for N insertions we make sure time is only O(NLogK)\n- Not NlogN. \n- We also never push neg vals, as it will indeed decrease our sum.\n- In edge case of 0 edges all node vals neg, we need to take neg val.\n- We also take it as we iterate all nodes with currSum init as VAL[i]\n\n- NOTE: In case of MaxHeaps - it takes O(NLogN) bcoz u use it to find the max element one by one, also u push all the elements into PQ.\n\n\n\n# Complexity\n- Time complexity:O(N^2 LOG K)\n- Log K not Log N. This is the optimization.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(V+E) adj list\n- \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {\n        int N = vals.size();\n        int M = edges.size();\n        \n        vector<int> adj[N];\n        \n        for(auto e : edges){ // O(E)\n\n            adj[e[0]].push_back(e[1]);\n            adj[e[1]].push_back(e[0]);         \n        }\n\n        int maxSum = INT_MIN;\n\n        for(int i=0; i<N; i++){ // O(N)\n            int currSum = vals[i]; // star sum = ur sum + ur adj sum upto k nodes\n            //we need min heap. So that atlast we have top k max ele\n            priority_queue<int,vector<int>,greater<int>> minH; //minheap\n\n            for(int adjN : adj[i] ){ //O(N) N in case of complete graphs\n                if(vals[adjN] > 0) // only enter pos vals bcoz we dont need neg at all\n                    minH.push(vals[adjN]); //O(Log K) \n                if(minH.size() > k) \n                    minH.pop(); // O(log k)\n\n                //we never allow minheap size to grow more than k \n            }\n\n            //minHeap now has Top K Max ele\n            while(!minH.empty()){ //O(K)\n                currSum += minH.top();\n                minH.pop();\n            }\n\n            maxSum = max(maxSum, currSum);\n\n        }\n\n        return maxSum;\n\n    }\n};\n```\n\n### **KINDLY UPVOTE IF U LIKED AND UNDERSTOOD**\n
['Graph', 'Heap (Priority Queue)', 'C++']