Problem Description

You are given an undirected graph with n nodes numbered from 0 to n - 1. Each node has a value given in the array vals, where vals[i] represents the value of node i. The graph's edges are provided in a 2D array edges, where each edges[i] = [ai, bi] indicates an undirected edge between nodes ai and bi.

A star graph is a special subgraph where one central node connects to zero or more other nodes directly. In other words, it's a subset of edges from the original graph where all edges share exactly one common node (the center).

The star sum is calculated by adding up the values of all nodes in the star graph - this includes the center node's value plus the values of all nodes connected to it.

Your task is to find the maximum possible star sum when the star graph contains at most k edges. This means you can choose any node as the center and connect it to up to k of its neighbors (or fewer if it doesn't have k neighbors).

For example, if a node with value 5 is the center and it connects to nodes with values 3, -2, and 7, and k = 2, you could choose to include the edges to nodes with values 3 and 7 (skipping the negative value -2) to get a star sum of 5 + 3 + 7 = 15.

The goal is to return the maximum star sum possible across all possible choices of center nodes and their edge selections.

Intuition

To maximize the star sum, we need to think about what makes a star graph's sum as large as possible. Since every star graph has a center node whose value we must include, and then we can choose up to k neighbors to connect to, the strategy becomes clear: for each potential center node, we want to greedily select its most valuable neighbors.

The key insight is that we should only include neighbors with positive values. Why? Because adding a neighbor with a negative value would decrease our total sum. Since we're allowed to use "at most" k edges (not exactly k), we can simply skip any negative-valued neighbors.

For each node that could serve as a center, we want to:

1. Start with the node's own value (this is mandatory)
2. Look at all its neighbors' values
3. Only consider neighbors with positive values (adding negative values would hurt our sum)
4. Sort these positive neighbor values in descending order
5. Take the top k values (or fewer if there aren't k positive neighbors)

By trying every node as a potential center and applying this greedy strategy, we can find the maximum possible star sum. The greedy approach works here because once we fix a center, the problem becomes independent - we're simply choosing the k largest positive values from the available neighbors, and there's no interaction between our choices that would require a more complex approach.

This leads us to preprocess the graph by creating adjacency lists that only store positive-valued neighbors for each node, sort these lists in descending order, and then for each node, calculate its potential star sum by taking its own value plus the sum of its top k positive neighbors.

Learn more about Greedy, Graph, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows the greedy strategy we identified by building an adjacency list that only stores positive-valued neighbors for each node.

First, we create a graph representation using a defaultdict(list) to store adjacency lists. As we process each edge [a, b], we make two key decisions:

• If vals[b] > 0, we add vals[b] to node a's adjacency list (since b would be a beneficial neighbor if a is the center)
• If vals[a] > 0, we add vals[a] to node b's adjacency list (since a would be a beneficial neighbor if b is the center)

This preprocessing step filters out negative-valued neighbors immediately, saving us from considering them later.

Next, we sort each node's adjacency list in descending order using bs.sort(reverse=True). This ensures that when we select neighbors for a star graph, we can simply take the first k elements to get the maximum possible contribution.

Finally, we calculate the maximum star sum by iterating through all nodes as potential centers. For each node i with value v:

• We compute its star sum as v + sum(g[i][:k])
• v is the center node's value (which we must include)
• g[i][:k] gives us the top k positive neighbor values (or all of them if there are fewer than k)
• The slice [:k] automatically handles cases where a node has fewer than k positive neighbors

The expression max(v + sum(g[i][:k]) for i, v in enumerate(vals)) efficiently finds the maximum star sum across all possible center choices. If a node has no positive neighbors, g[i] will be an empty list, and sum(g[i][:k]) will be 0, so the star sum will just be the node's own value.

This approach has a time complexity of O(E + V log V) where E is the number of edges (for building the graph) and V is the number of nodes (for sorting each adjacency list), and space complexity of O(E) for storing the adjacency lists.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• n = 5 nodes (numbered 0 to 4)
• vals = [10, -5, 3, 8, -2] (node values)
• edges = [[0,1], [0,2], [0,3], [1,4], [2,3]] (connections)
• k = 2 (maximum edges in star graph)

Step 1: Build the filtered adjacency list

We process each edge and only add positive-valued neighbors:

• Edge [0,1]:

  • Node 1 has value -5 (negative), so we don't add it to node 0's list
  • Node 0 has value 10 (positive), so we add 10 to node 1's list

• Edge [0,2]:

  • Node 2 has value 3 (positive), so we add 3 to node 0's list
  • Node 0 has value 10 (positive), so we add 10 to node 2's list

• Edge [0,3]:

  • Node 3 has value 8 (positive), so we add 8 to node 0's list
  • Node 0 has value 10 (positive), so we add 10 to node 3's list

• Edge [1,4]:

  • Node 4 has value -2 (negative), so we don't add it to node 1's list
  • Node 1 has value -5 (negative), so we don't add it to node 4's list

• Edge [2,3]:

  • Node 3 has value 8 (positive), so we add 8 to node 2's list
  • Node 2 has value 3 (positive), so we add 3 to node 3's list

Resulting adjacency lists:

• g[0] = [3, 8] (positive neighbors of node 0)
• g[1] = [10] (positive neighbors of node 1)
• g[2] = [10, 8] (positive neighbors of node 2)
• g[3] = [10, 3] (positive neighbors of node 3)
• g[4] = [] (no positive neighbors)

Step 2: Sort each adjacency list in descending order

• g[0] = [8, 3] (sorted)
• g[1] = [10] (already sorted)
• g[2] = [10, 8] (already sorted)
• g[3] = [10, 3] (already sorted)
• g[4] = [] (empty)

Step 3: Calculate star sum for each potential center

For each node as center, take its value plus the sum of its top k=2 neighbors:

• Node 0 as center: 10 + sum([8, 3][:2]) = 10 + 8 + 3 = 21
• Node 1 as center: -5 + sum([10][:2]) = -5 + 10 = 5
• Node 2 as center: 3 + sum([10, 8][:2]) = 3 + 10 + 8 = 21
• Node 3 as center: 8 + sum([10, 3][:2]) = 8 + 10 + 3 = 21
• Node 4 as center: -2 + sum([][:2]) = -2 + 0 = -2

Step 4: Return the maximum star sum

The maximum star sum is 21, which can be achieved by choosing node 0, 2, or 3 as the center.

When node 0 is the center, we form a star with edges to nodes 2 and 3 (values 3 and 8), giving us 10 + 3 + 8 = 21. This demonstrates how the greedy approach of selecting the k most valuable positive neighbors maximizes the star sum.

Solution Implementation

Time and Space Complexity

Time Complexity: O(E + V*log(V) + V*k) where E is the number of edges, V is the number of vertices (nodes), and k is the maximum number of edges allowed in a star graph.

• Building the adjacency list takes O(E) time as we iterate through all edges once
• For each vertex that has neighbors, we sort its neighbor values. In the worst case, a vertex could be connected to all other V-1 vertices, so sorting takes O(V*log(V)) time per vertex with neighbors
• The total sorting complexity across all vertices is bounded by O(E*log(V)) since the total number of neighbor entries across all vertices is at most 2*E
• Finding the maximum star sum requires iterating through all V vertices and for each vertex, summing up to k values from its sorted neighbor list, which takes O(V*k) time

Space Complexity: O(E)

• The adjacency list g stores at most 2*E values (each edge contributes two entries in the worst case when both node values are positive)
• The sorting is done in-place, so no additional space is required for sorting
• The space for storing the input is not counted as extra space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle k = 0 Case

A critical edge case occurs when k = 0, meaning the star graph cannot have any edges. In this scenario, the star graph consists of only a single node (the center) with no connections. The maximum star sum would simply be the maximum value among all nodes.

Why this happens: Developers often focus on the general case where k > 0 and overlook that k = 0 is a valid input according to the problem constraints.

The issue: The current solution actually handles this correctly because graph[node_idx][:0] returns an empty list, and sum([]) returns 0. However, it's not immediately obvious that this edge case is covered, which can lead to confusion during code review or debugging.

2. Including Negative-Valued Neighbors When Node Has Fewer Than k Positive Neighbors

A common mistake is thinking that if a node has fewer than k positive neighbors, you must include negative neighbors to reach exactly k edges.

Example scenario:

• Node 0 has value 10
• Node 0's neighbors have values [5, 3, -2, -7]
• k = 3

Incorrect approach: Include values [5, 3, -2] to get exactly 3 edges, resulting in sum = 10 + 5 + 3 - 2 = 16

Correct approach: Only include positive values [5, 3], resulting in sum = 10 + 5 + 3 = 18

Why this happens: The problem states "at most k edges," but developers might misinterpret this as needing to use exactly k edges when possible.

3. Double-Counting the Center Node's Value

When building the adjacency list, a subtle bug can occur if you accidentally include the center node's value in its own adjacency list or count it twice when calculating the star sum.

Incorrect implementation example:

# Wrong: might add node's own value to its neighbor list
for node_a, node_b in edges:
    graph[node_a].append(vals[node_a])  # Wrong!
    graph[node_b].append(vals[node_b])  # Wrong!

Solution: Always ensure that the adjacency list for a node contains only its neighbors' values, not its own value. The center's value should be added exactly once when calculating the star sum.

4. Not Considering Isolated Nodes

If a node has no edges in the input (isolated node), it won't appear in the edges array, but it's still a valid candidate for being a star center with 0 edges.

Why this matters: An isolated node with a high positive value could potentially be the answer, especially when all other nodes have negative values or form stars with lower sums.

Solution: The current implementation handles this correctly by iterating through all nodes via enumerate(vals) rather than only considering nodes that appear in edges. This ensures isolated nodes are evaluated as potential star centers.