LeetCode 2497 - Maximum Star Sum of a Graph

LeetCode Problem 2497

Difficulty: 🟡 Medium
Topics: Array, Greedy, Graph Theory, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us an undirected graph where each node has an associated integer value. We are asked to form a star graph and compute the maximum possible star sum.

A star graph is defined by choosing one node as the center and selecting up to k of its neighbors. The resulting star sum is the value of the center node plus the values of all selected neighboring nodes.

The key detail is that we are allowed to select fewer than k neighbors, including zero neighbors. This matters because some neighbors may have negative values, and including them would reduce the total sum.

The input consists of:

• vals, where vals[i] is the value assigned to node i
• edges, representing undirected connections between nodes
• k, the maximum number of neighbors that may be included in the star

The output is the largest possible star sum over all valid star graphs.

The constraints are important:

• n can be as large as 10^5
• The number of edges can also be up to 10^5

These limits immediately rule out expensive graph processing approaches such as repeatedly sorting large neighbor sets for every node without care, or exploring all possible subsets of neighbors.

A few important observations emerge from the problem statement:

1. Since the graph is undirected, every edge contributes to the neighbor list of both endpoints.
2. We never want to include a negative-valued neighbor because we are allowed to choose fewer than k neighbors.
3. For a fixed center node, the optimal strategy is always to choose the largest positive neighbor values, up to k of them.
4. The center node itself must always be included, even if its value is negative.

Several edge cases are important:

• k = 0, meaning no neighbors may be chosen
• Graphs with only negative values
• Isolated nodes with no neighbors
• Large dense neighbor lists
• Situations where fewer than k positive neighbors exist

A correct solution must handle all of these efficiently.

Approaches

Brute Force Approach

A brute-force solution would examine every node as a potential center. For each node, we would generate all subsets of its neighbors containing at most k nodes, compute the corresponding star sums, and keep the maximum.

This works because every possible valid star graph is explicitly considered.

However, this becomes computationally infeasible very quickly. If a node has degree d, there are exponentially many subsets of neighbors:

$$\sum_{i=0}^{k} \binom{d}{i}$$

In the worst case, a node may have nearly 10^5 neighbors, making exhaustive subset generation impossible.

Even a slightly improved brute-force version that sorts neighbors for every node independently can still become inefficient if done carelessly.

Key Insight

The important observation is that negative neighbors should never be included.

Suppose a center node has neighbors with values:

[5, -2, 7, 1]

If k = 2, the optimal choice is simply the two largest positive values:

7 and 5

There is never a reason to include -2.

Therefore, for every node:

1. Collect the values of its neighbors
2. Keep only positive values
3. Select the largest k values
4. Add them to the center node value

This transforms the problem into a straightforward greedy selection problem.

We can efficiently build adjacency information and process each node independently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n + m)	Enumerates neighbor subsets
Optimal	O(m log m)	O(n + m)	Greedily selects largest positive neighbors

Algorithm Walkthrough

1. Create an adjacency list where each node stores the positive values of its neighbors.

Since negative neighbors are never beneficial, we only need to store positive neighbor values. For every edge [u, v]:

• If vals[v] > 0, add vals[v] to node u
• If vals[u] > 0, add vals[u] to node v

This reduces unnecessary work later. 2. Initialize the answer.

Since a valid star graph may contain only the center node itself, initialize the result as the maximum node value in vals. 3. Process each node independently.

For every node:

• Sort its positive neighbor values in descending order
• Take up to the first k values
• Add them to the center node value
• Update the global maximum

4. Return the maximum star sum found.

Why it works

For a fixed center node, every included neighbor contributes independently to the total sum.

Since we may choose fewer than k neighbors, any negative contribution should be excluded. Therefore, the optimal star for a center node always consists of the largest positive neighbor values.

Because this logic is independently optimal for every center node, checking all centers guarantees that the global maximum is found.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        neighbors = defaultdict(list)

        for u, v in edges:
            if vals[v] > 0:
                neighbors[u].append(vals[v])

            if vals[u] > 0:
                neighbors[v].append(vals[u])

        best = max(vals)

        for node in range(len(vals)):
            positive_neighbors = neighbors[node]
            positive_neighbors.sort(reverse=True)

            current_sum = vals[node]

            for i in range(min(k, len(positive_neighbors))):
                current_sum += positive_neighbors[i]

            best = max(best, current_sum)

        return best

The implementation begins by constructing an adjacency structure that stores only positive-valued neighbors. This is an optimization based on the observation that negative neighbors can never improve a star sum.

The variable best is initialized to the maximum node value because every node alone forms a valid star graph with zero edges.

For each node, the positive neighbor values are sorted in descending order. The algorithm then greedily takes the top k values, since these produce the largest possible increase to the star sum.

Finally, the maximum value across all centers is returned.

Go Solution

package main

import (
	"sort"
)

func maxStarSum(vals []int, edges [][]int, k int) int {
	n := len(vals)

	neighbors := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		if vals[v] > 0 {
			neighbors[u] = append(neighbors[u], vals[v])
		}

		if vals[u] > 0 {
			neighbors[v] = append(neighbors[v], vals[u])
		}
	}

	best := vals[0]

	for _, value := range vals {
		if value > best {
			best = value
		}
	}

	for i := 0; i < n; i++ {
		sort.Sort(sort.Reverse(sort.IntSlice(neighbors[i])))

		currentSum := vals[i]

		limit := k
		if len(neighbors[i]) < limit {
			limit = len(neighbors[i])
		}

		for j := 0; j < limit; j++ {
			currentSum += neighbors[i][j]
		}

		if currentSum > best {
			best = currentSum
		}
	}

	return best
}

The Go implementation follows the same algorithmic structure as the Python solution.

Instead of Python dictionaries, Go uses a slice of slices for adjacency storage. Sorting is handled using sort.Sort(sort.Reverse(...)).

Go slices naturally handle empty neighbor lists, so isolated nodes require no special handling.

The constraints ensure that integer overflow is not an issue for Go's standard int type.

Worked Examples

Example 1

vals = [1,2,3,4,10,-10,-20]
edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]
k = 2

Step 1: Build Positive Neighbor Lists

Edge	Action
[0,1]	node 0 gets 2, node 1 gets 1
[1,2]	node 1 gets 3, node 2 gets 2
[1,3]	node 1 gets 4, node 3 gets 2
[3,4]	node 3 gets 10, node 4 gets 4
[3,5]	node 3 ignores -10, node 5 gets 4
[3,6]	node 3 ignores -20, node 6 gets 4

Final neighbor lists:

Node	Positive Neighbors
0	[2]
1	[1, 3, 4]
2	[2]
3	[2, 10]
4	[4]
5	[4]
6	[4]

Step 2: Compute Star Sums

Center	Top k Neighbors	Star Sum
0	[2]	1 + 2 = 3
1	[4,3]	2 + 4 + 3 = 9
2	[2]	3 + 2 = 5
3	[10,2]	4 + 10 + 2 = 16
4	[4]	10 + 4 = 14
5	[4]	-10 + 4 = -6
6	[4]	-20 + 4 = -16

Maximum result:

16

Example 2

vals = [-5]
edges = []
k = 0

There are no neighbors.

The only possible star graph contains node 0 alone.

Center	Star Sum
0	-5

Result:

-5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log m)	Neighbor lists are sorted
Space	O(n + m)	Adjacency storage

Let m be the number of edges.

Each edge is processed once while building adjacency lists. Across all nodes, the total number of stored positive neighbor entries is at most 2m.

The dominant cost comes from sorting neighbor lists. In the worst case, one node may contain nearly all neighbor values, leading to a total sorting cost of O(m log m).

The adjacency structure requires O(n + m) space.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:
        neighbors = defaultdict(list)

        for u, v in edges:
            if vals[v] > 0:
                neighbors[u].append(vals[v])

            if vals[u] > 0:
                neighbors[v].append(vals[u])

        best = max(vals)

        for node in range(len(vals)):
            positive_neighbors = neighbors[node]
            positive_neighbors.sort(reverse=True)

            current_sum = vals[node]

            for i in range(min(k, len(positive_neighbors))):
                current_sum += positive_neighbors[i]

            best = max(best, current_sum)

        return best

solution = Solution()

assert solution.maxStarSum(
    [1,2,3,4,10,-10,-20],
    [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]],
    2
) == 16  # provided example

assert solution.maxStarSum(
    [-5],
    [],
    0
) == -5  # single node graph

assert solution.maxStarSum(
    [5,1,2],
    [[0,1],[0,2]],
    0
) == 5  # k = 0 means center only

assert solution.maxStarSum(
    [1,-2,3],
    [[0,1],[0,2]],
    2
) == 4  # negative neighbor excluded

assert solution.maxStarSum(
    [-1,-2,-3],
    [[0,1],[1,2]],
    2
) == -1  # all negative values

assert solution.maxStarSum(
    [10,20,30],
    [],
    2
) == 30  # disconnected graph

assert solution.maxStarSum(
    [1,2,3,4],
    [[0,1],[0,2],[0,3]],
    5
) == 10  # k larger than degree

assert solution.maxStarSum(
    [100,-50,50,40],
    [[0,1],[0,2],[0,3]],
    1
) == 150  # choose only largest neighbor

assert solution.maxStarSum(
    [0,0,0],
    [[0,1],[1,2]],
    2
) == 0  # zero-valued nodes

assert solution.maxStarSum(
    [5,-100,6],
    [[0,1],[1,2]],
    2
) == 6  # isolated optimal center

Test Summary

Test	Why
Example 1	Standard mixed graph
Example 2	Single node edge case
k = 0	Ensures neighbors are excluded
Negative neighbor	Confirms greedy exclusion
All negative values	Verifies best standalone node
No edges	Tests disconnected graph
k larger than degree	Ensures bounds handled safely
Select largest neighbor	Validates greedy ordering
Zero-valued nodes	Tests neutral contributions
Negative center connections	Ensures independent center evaluation

Edge Cases

Case 1: k = 0

When k is zero, the star graph cannot include any edges. A buggy implementation might still attempt to add neighbors or fail due to empty iterations.

The implementation handles this naturally because the loop that adds neighbor values executes zero times. Each node contributes only its own value.

Case 2: All Neighbor Values Are Negative

Suppose a node has many neighbors, but every neighbor has a negative value. Including any of them would decrease the total star sum.

A naive implementation that always selects exactly k neighbors would produce incorrect results.

This solution explicitly filters out non-positive neighbors while building adjacency lists, ensuring only beneficial neighbors are considered.

Case 3: Large k Compared to Node Degree

A node may have fewer than k neighbors. Without careful bounds checking, this can cause index errors or out-of-range access.

The implementation safely uses:

min(k, len(positive_neighbors))

so only existing neighbors are processed.

Case 4: Isolated Nodes

Some nodes may have no edges at all. Since a single node alone is still a valid star graph, isolated nodes must still be considered.

The solution initializes the answer with max(vals), guaranteeing that even completely disconnected nodes are handled correctly.