# 2497. Maximum Star Sum of a Graph

• Time: $O(|E| + n\cdot (a\log a + k))$, where $a$ is # of all the adjacent nodes of each node
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int maxStarSum(vector& vals, vector>& edges, int k) { const int n = vals.size(); int ans = INT_MIN; vector>> graph(n); for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; graph[u].emplace_back(v, vals[v]); graph[v].emplace_back(u, vals[u]); } for (int i = 0; i < n; ++i) { priority_queue maxHeap; for (const auto& [_, val] : graph[i]) if (val > 0) maxHeap.push(val); int starSum = vals[i]; for (int j = 0; j < k && !maxHeap.empty(); ++j) starSum += maxHeap.top(), maxHeap.pop(); ans = max(ans, starSum); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public int maxStarSum(int[] vals, int[][] edges, int k) { final int n = vals.length; int ans = Integer.MIN_VALUE; List>[] graph = new List[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; graph[u].add(new Pair<>(v, vals[v])); graph[v].add(new Pair<>(u, vals[u])); } for (int i = 0; i < n; ++i) { Queue maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (Pair pair : graph[i]) { final int val = pair.getValue(); if (val > 0) maxHeap.offer(val); } int starSum = vals[i]; for (int j = 0; j < k && !maxHeap.isEmpty(); ++j) starSum += maxHeap.poll(); ans = Math.max(ans, starSum); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int: n = len(vals) ans = -math.inf graph = [[] for _ in range(n)] for u, v in edges: graph[u].append((v, vals[v])) graph[v].append((u, vals[u])) for i, starSum in enumerate(vals): maxHeap = [] for _, val in graph[i]: if val > 0: heapq.heappush(maxHeap, -val) j = 0 while j < k and maxHeap: starSum -= heapq.heappop(maxHeap) j += 1 ans = max(ans, starSum) return ans