Easy to understand | Optimized solution | Beat 100% | DETAILED EXPLANATIONS WITH COMPLEXITY
\n\n\n\n\n# Intuition\nSince it is certain that a graph will have a center node, [graph is undirected ] and we can choose any node as a center.\nHence we can gr
![image.png](https://assets.leetcode.com/users/images/cdc34732-9381-49b9-b5e7-11ca1a691fb2_1726000648.6170845.png)\n\n\n\n\n# Intuition\nSince it is certain that a graph will have a center node, [graph is undirected ] and we can choose any node as a center.\nHence we can greedly try all node as center node and consume at most k edge to get the max star graph sum of subgraph centered around selected node. \n\n# Approach\n\n\n* Graph Construction:\nBuild an adjacency list for the graph.\nInstead of storing node values directly, use a min heap of size ( $$k$$ ) to store the maximum ( $$k$$ ) node values for each node. This allows efficient extraction of the top ( $$k$$ ) values later.\n\n* Processing Each Node:\nAfter constructing the graph, treat each node as a potential center node.\nFor each node, use the min heap to include the top ( $$k$$ ) node values from its neighbors.\n\n* Calculate Maximum Sum:\nFor each potential center node, calculate the sum of its value and the values of the top ( $$k$$ ) nodes from the priority queue.\nTrack and return the maximum sum obtained.\n\n\n# Complexity\n- Time complexity:\n$$O(EK*Log(K))$$ +  $$O(N*k*Log(k))$$ = $$O(max(N,E)*k*Log(k))$$\n\n- Space complexity:\n$$O(NK)$$\n\n\n# Code\n```java []\npublic int maxStarSum(int[] vals, int[][] edges, int k) {\n            if (vals == null || vals.length == 0)\n                return Integer.MIN_VALUE;\n\n            if (k == 0 || edges == null || edges.length == 0 || edges[0].length == 0)\n                return Arrays.stream(vals).max().getAsInt();\n\n            //generate graph as adj list O (EK*Log(K))\n            PriorityQueue<Integer>[] graphAdjList = buildGraphAdjList(edges, vals, k);\n\n            //consider each node as a potential center node and try to include top k nodes from PQ\n            int maxSum = Integer.MIN_VALUE;\n\n            //O(N)*O(k*Log(k)) = O(N*k*Log(k))\n            for (int i = 0; i < graphAdjList.length; i++) {\n                int sum = vals[i];\n                PriorityQueue<Integer> pq = graphAdjList[i];\n                //O(k*Log(k))\n                while (!pq.isEmpty())\n                    sum += pq.poll();\n\n                maxSum = Math.max(maxSum, sum);\n            }\n\n\n            return maxSum;\n\n\n        }\n\n        /**\n         * T/S : O (EK*Log(K))\n         *\n         * @param edges\n         * @param nodeValues\n         * @param k\n         * @return PriorityQueue<Integer>[]\n         */\n        private PriorityQueue<Integer>[] buildGraphAdjList(int[][] edges, int[] nodeValues, int k) {\n\n            //Build a graph, where each connected node value is stored as min heap containing largest k nodes values [ min heap as max heap of k nodes ]\n            PriorityQueue<Integer>[] graphAdjList = new PriorityQueue[nodeValues.length];\n            for (int i = 0; i < nodeValues.length; i++)\n                graphAdjList[i] = new PriorityQueue<>();\n\n            //build graph\n            //T: O(E) * O(k*Log(k))\n            for (int[] edge : edges) {\n                int u = edge[0];\n                int v = edge[1];\n\n                // for the u-v edge, if u is positive, then add it to our min heap (of max elements)\n                if (nodeValues[v] > 0) {\n                    PriorityQueue<Integer> pq = graphAdjList[u];\n                    offer(pq, nodeValues[v], k);\n\n                }\n\n                // for the v-u edge, if u is positive, then add it to our min heap (of max elements)\n                if (nodeValues[u] > 0) {\n                    PriorityQueue<Integer> pq = graphAdjList[v];\n                    offer(pq, nodeValues[u], k);\n                }\n\n            }\n            return graphAdjList;\n        }\n\n        //T: O(k*Log(k))\n        private void offer(PriorityQueue<Integer> pq, int element, int k) {\n            pq.offer(element);\n            if (pq.size() > k)\n                pq.poll();\n        }\n\n```\n\n# Optimized Approach\nThe optimization can be achieved by calculating and maximizing the sum dynamically while constructing the graph.\n\n# Complexity\n- Time complexity:\n$$O(EK*Log(K))$$ \n\n- Space complexity:\n$$O(NK)$$\n\n# Code\n```java []\nclass Solution {\n       public int maxStarSum(int[] vals, int[][] edges, int k) {\n            if (vals == null || vals.length == 0)\n                return Integer.MIN_VALUE;\n\n            if (k == 0 || edges == null || edges.length == 0 || edges[0].length == 0)\n                return Arrays.stream(vals).max().getAsInt();\n\n            return buildGraphAdjList(edges, vals, k);\n\n        }\n\n        /**\n         * T/S : O (EK*Log(K))\n         *\n         * @param edges\n         * @param nodeValues\n         * @param k\n         * @return PriorityQueue<Integer>[]\n         */\n        private int buildGraphAdjList(int[][] edges, int[] nodeValues, int k) {\n\n            int[] sum = new int[nodeValues.length];\n            int maxSum = Arrays.stream(nodeValues).max().getAsInt();\n            //Build a graph, where each connected node value is stored as min heap containing largest k nodes values [ min heap as max heap of k nodes ]\n            PriorityQueue<Integer>[] graphAdjList = new PriorityQueue[nodeValues.length];\n            for (int i = 0; i < nodeValues.length; i++) {\n                sum[i] = nodeValues[i];\n                graphAdjList[i] = new PriorityQueue<>();\n            }\n\n            //build graph\n            //T: O(E) * O(k*Log(k))\n            for (int[] edge : edges) {\n                int u = edge[0];\n                int v = edge[1];\n\n                // for the u-v edge, if u is positive, then add it to our min heap (of max elements)\n                if (nodeValues[v] > 0) {\n                    PriorityQueue<Integer> pq = graphAdjList[u];\n                    offer(pq, nodeValues[v], k, sum, u);\n                    maxSum = Math.max(Math.max(sum[u], nodeValues[v]),maxSum);\n\n\n                }\n\n                // for the v-u edge, if u is positive, then add it to our min heap (of max elements)\n                if (nodeValues[u] > 0) {\n                    PriorityQueue<Integer> pq = graphAdjList[v];\n                    offer(pq, nodeValues[u], k, sum, v);\n                    maxSum = Math.max(Math.max(sum[v], nodeValues[u]),maxSum);\n                }\n\n                //in case both node values are negative, then we have to choose the maximum out of it\n                maxSum = Math.max(maxSum, Math.max(nodeValues[u], nodeValues[v]));\n\n            }\n            return maxSum;\n        }\n\n        //T: O(k*Log(k))\n        private void offer(PriorityQueue<Integer> pq, int element, int k, int[] sum, int uv) {\n\n            pq.offer(element);\n\n            int polledElement = 0;\n            if (pq.size() > k) {\n                polledElement = pq.poll();\n            }\n\n\n            sum[uv] += element - polledElement;\n\n        }\n}\n```
['Heap (Priority Queue)', 'Java']