Skip to content

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<int>& vals, vector<vector<int>>& edges, int k) {
    const int n = vals.size();
    int ans = INT_MIN;
    vector<vector<pair<int, int>>> graph(n);

    for (const vector<int>& 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<int> 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<Pair<Integer, Integer>>[] 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<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
      for (Pair<Integer, Integer> 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