2497. Maximum Star Sum of a Graph LeetCode Solution

In this guide, you will get 2497. Maximum Star Sum of a Graph LeetCode Solution with the best time and space complexity. The solution to Maximum Star Sum of a Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Star Sum of a Graph solution in C++
Maximum Star Sum of a Graph solution in Java
Maximum Star Sum of a Graph solution in Python
Additional Resources

2497. Maximum Star Sum of a Graph LeetCode Solution image

Problem Statement of Maximum Star Sum of a Graph

There is an undirected graph consisting of n nodes numbered from 0 to n – 1. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node.
You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.
The image below shows star graphs with 3 and 4 neighbors respectively, centered at the blue node.

The star sum is the sum of the values of all the nodes present in the star graph.
Given an integer k, return the maximum star sum of a star graph containing at most k edges.

Example 1:

Input: vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
Output: 16
Explanation: The above diagram represents the input graph.
The star graph with the maximum star sum is denoted by blue. It is centered at 3 and includes its neighbors 1 and 4.
It can be shown it is not possible to get a star graph with a sum greater than 16.

Example 2:

Input: vals = [-5], edges = [], k = 0
Output: -5
Explanation: There is only one possible star graph, which is node 0 itself.
Hence, we return -5.

Constraints:

n == vals.length
1 <= n <= 105
-104 <= vals[i] <= 104
0 <= edges.length <= min(n * (n – 1) / 2, 105)
edges[i].length == 2
0 <= ai, bi <= n – 1
ai != bi
0 <= k <= n – 1

Complexity Analysis

Time Complexity: O(|E| + n\cdot (a\log a + k)), where a is # of all the adjacent nodes of each node
Space Complexity: O(|V| + |E|)

2497. Maximum Star Sum of a Graph LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2497. Maximum Star Sum of a Graph LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2497. Maximum Star Sum of a Graph LeetCode Solution in Python

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
 # code by PROGIEZ