Maximum Star Sum of a Graph

Med

#2278Time: O(E + Σ(deg(i) * log(deg(i)))) over all nodes `i`. A simpler upper bound is `O(E * log N)`, where `E` is the number of edges and `N` is the number of nodes. Building the adjacency list takes `O(E)`. For each node `i`, we sort its neighbors, taking `O(deg(i) * log(deg(i)))`. The sum of degrees `Σdeg(i)` is `2*E`.Space: O(E + N), where `E` is the number of edges and `N` is the number of nodes. This is for the adjacency list and the temporary list for sorting neighbor values (which can be up to size `N-1` in the worst case).1 company

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)Graph

Companies

Akuna Capital

Prompt

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 i^th node.

You are also given a 2D integer array edges where edges[i] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

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 <= 10⁵
-10⁴ <= vals[i] <= 10⁴
0 <= edges.length <= min(n * (n - 1) / 2, 10⁵)
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
0 <= k <= n - 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each node, considering it as a potential center of a star graph. For each potential center, it calculates the maximum possible star sum by adding the values of its k most valuable neighbors. To find these neighbors, it collects the values of all neighbors, filters for positive ones, sorts them in descending order, and picks the top k. The overall maximum sum found across all possible centers is the answer.

Algorithm

Create an adjacency list to represent the graph from the edges array.
Initialize a variable maxSum to Integer.MIN_VALUE.
Iterate through each node i from 0 to n-1, treating it as the center of a star graph.
For each center i, initialize currentSum = vals[i].
Create a list to store the values of its neighbors.
Iterate through the neighbors of i using the adjacency list. If a neighbor's value is positive, add it to the list.
Sort the list of positive neighbor values in descending order.
Add the top k values (or fewer if the list is smaller than k) from the sorted list to currentSum.
Update maxSum with the maximum of maxSum and currentSum.
After iterating through all nodes, return maxSum.

Walkthrough

The core idea is to check every node as a potential center for the star graph.

First, we need an efficient way to access the neighbors of any given node. An adjacency list is a suitable data structure for this, which can be built by iterating through the edges array once.

We initialize a variable maxSum to the smallest possible integer value to keep track of the maximum star sum found so far.

Then, we loop through each node i from 0 to n-1.

For each node i, we calculate the potential star sum with i as the center. The sum starts with vals[i].
We gather the values of all neighbors of i. We are only interested in neighbors that increase the total sum, so we only consider neighbors with positive values.
We store these positive neighbor values in a list.
To pick the best k neighbors, we sort this list of positive values in descending order.
We then iterate up to k times (or until we run out of positive neighbors) and add the values from the sorted list to our current sum.
After calculating the maximum possible sum for the center i, we update maxSum = max(maxSum, currentSum).

After checking all nodes as potential centers, maxSum will hold the final answer.

1import java.util.*;2 3class Solution {4    public int maxStarSum(int[] vals, int[][] edges, int k) {5        int n = vals.length;6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10 11        for (int[] edge : edges) {12            adj.get(edge[0]).add(edge[1]);13            adj.get(edge[1]).add(edge[0]);14        }15 16        int maxSum = Integer.MIN_VALUE;17 18        for (int i = 0; i < n; i++) {19            int currentSum = vals[i];20            List<Integer> neighborValues = new ArrayList<>();21            for (int neighbor : adj.get(i)) {22                if (vals[neighbor] > 0) {23                    neighborValues.add(vals[neighbor]);24                }25            }26 27            Collections.sort(neighborValues, Collections.reverseOrder());28 29            for (int j = 0; j < Math.min(k, neighborValues.size()); j++) {30                currentSum += neighborValues.get(j);31            }32            33            maxSum = Math.max(maxSum, currentSum);34        }35 36        return maxSum;37    }38}

Complexity

Time

O(E + Σ(deg(i) * log(deg(i)))) over all nodes `i`. A simpler upper bound is `O(E * log N)`, where `E` is the number of edges and `N` is the number of nodes. Building the adjacency list takes `O(E)`. For each node `i`, we sort its neighbors, taking `O(deg(i) * log(deg(i)))`. The sum of degrees `Σdeg(i)` is `2*E`.

Space

O(E + N), where `E` is the number of edges and `N` is the number of nodes. This is for the adjacency list and the temporary list for sorting neighbor values (which can be up to size `N-1` in the worst case).

Trade-offs

Pros

Relatively straightforward to understand and implement.
Correctly solves the problem.

Cons

Sorting all positive neighbors for each node can be inefficient, especially if k is small compared to the node's degree. We only need the top k elements, not a fully sorted list.

This approach improves upon the sorting method. Instead of sorting all positive neighbor values for each center node, it uses a min-heap (Priority Queue) of size k to efficiently find the k largest positive neighbor values. This avoids the cost of a full sort, making it more efficient, especially when a node has many neighbors but k is small.

Algorithm

Create an adjacency list to represent the graph.
Initialize maxSum to Integer.MIN_VALUE.
Iterate through each node i from 0 to n-1 as a potential center.
For each center i, initialize currentSum = vals[i].
Create a min-heap (PriorityQueue) to keep track of the largest neighbor values.
Iterate through the neighbors of i. For each neighbor j with vals[j] > 0:
- Add vals[j] to the heap.
- If the heap's size is greater than k, remove the smallest element from the heap (poll()).
After iterating through all neighbors, sum the elements remaining in the heap and add them to currentSum.
Update maxSum = max(maxSum, currentSum).
After checking all nodes, return maxSum.

Walkthrough

Similar to the first approach, we iterate through each node i as a potential center. The graph representation is also an adjacency list.

The key difference lies in how we select the top k neighbors. Instead of collecting all positive neighbor values and sorting them, we use a min-heap of a fixed maximum size k.

For each center node i, we initialize its star sum currentSum = vals[i].

We create a min-heap (in Java, PriorityQueue).
We iterate through the neighbors of i. For each neighbor j with a positive value vals[j]:
- We add vals[j] to the min-heap.
- If the size of the heap exceeds k, we remove the smallest element (the root of the min-heap). This ensures the heap always contains the k largest values seen so far for the current center's neighbors.
After checking all neighbors of i, the heap contains up to k of the largest positive neighbor values.
We sum up all the values in the heap and add them to currentSum.
We then update the global maxSum with this currentSum if it's larger.

This process is repeated for all nodes, and the final maxSum is returned.

1import java.util.*;2 3class Solution {4    public int maxStarSum(int[] vals, int[][] edges, int k) {5        int n = vals.length;6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10 11        for (int[] edge : edges) {12            adj.get(edge[0]).add(edge[1]);13            adj.get(edge[1]).add(edge[0]);14        }15 16        int maxSum = Integer.MIN_VALUE;17 18        for (int i = 0; i < n; i++) {19            int currentSum = vals[i];20            // Min-heap to store the k largest positive neighbor values21            PriorityQueue<Integer> pq = new PriorityQueue<>();22 23            for (int neighbor : adj.get(i)) {24                if (vals[neighbor] > 0) {25                    pq.add(vals[neighbor]);26                    if (pq.size() > k) {27                        pq.poll();28                    }29                }30            }31 32            while (!pq.isEmpty()) {33                currentSum += pq.poll();34            }35            36            maxSum = Math.max(maxSum, currentSum);37        }38 39        return maxSum;40    }41}

Complexity

Time

O(E * log k). Building the adjacency list is `O(E)`. For each node `i`, we iterate through its `deg(i)` neighbors. Each heap operation takes `O(log k)` time. The total time for the main loop is `Σ(deg(i) * log k)` over all `i`, which is `2*E*log(k)`.

Space

O(E + k). `O(E)` for the adjacency list and `O(k)` for the priority queue used for each node.

Trade-offs

Pros

More efficient than the sorting approach, especially when k is small.
It's an optimal approach for the given constraints.

Cons

Slightly more complex to implement due to the use of a priority queue.

Solutions

Solution

1class Solution {2public3  int maxStarSum(int[] vals, int[][] edges, int k) {4    int n = vals.length;5    List<Integer>[] g = new List[n];6    Arrays.setAll(g, key->new ArrayList<>());7    for (var e : edges) {8      int a = e[0], b = e[1];9      if (vals[b] > 0) {10        g[a].add(vals[b]);11      }12      if (vals[a] > 0) {13        g[b].add(vals[a]);14      }15    }16    for (var e : g) {17      Collections.sort(e, (a, b)->b - a);18    }19    int ans = Integer.MIN_VALUE;20    for (int i = 0; i < n; ++i) {21      int v = vals[i];22      for (int j = 0; j < Math.min(g[i].size(), k); ++j) {23        v += g[i].get(j);24      }25      ans = Math.max(ans, v);26    }27    return ans;28  }29}

1class Solution {2public:3  int maxStarSum(vector<int> &vals, vector<vector<int>> &edges, int k) {4    int n = vals.size();5    vector<vector<int>> g(n);6    for (auto &e : edges) {7      int a = e[0], b = e[1];8      if (vals[b] > 0)9        g[a].emplace_back(vals[b]);10      if (vals[a] > 0)11        g[b].emplace_back(vals[a]);12    }13    for (auto &e : g)14      sort(e.rbegin(), e.rend());15    int ans = INT_MIN;16    for (int i = 0; i < n; ++i) {17      int v = vals[i];18      for (int j = 0; j < min((int)g[i].size(), k); ++j)19        v += g[i][j];20      ans = max(ans, v);21    }22    return ans;23  }24};

1class Solution:2    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int: g = defaultdict(list) for a, b in edges: if vals[b] > 0: g[a]. append(vals[b]) if vals[a] > 0: g[b]. append(vals[a]) for bs in g . values(): bs . sort(reverse=True) return max(v + sum(g[i][: k]) for i, v in enumerate(vals))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem