Maximum Star Sum of a Graph
MediumUpdated: Jul 30, 2025
Practice on:
Problem
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.
graph TD; subgraph S1[" "] A(" ") --- B(" ") & C(" ") & D(" ") end subgraph S2[" "] E(" ") --- F(" ") --- G(" ") H(" ") --- F F --- I(" ") end classDef blue fill:#87CEEB,stroke:#333,stroke-width:2px; class A blue class F blue
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.
Examples
Example 1:
graph TD A0(num: 0<br> val: 1) A1(num: 1<br> val: 2) A2(num: 2<br> val: 3) A3(num: 3<br> val: 4) A4(num: 4<br> val: 10) A5(num: 5<br> val: -10) A6(num: 6<br> val: -20) A0 --- A1 A1 --- A2 A1 --- A3 A3 --- A4 A3 --- A5 A3 --- A6 linkStyle 2 stroke:#1e90ff,stroke-width:4px linkStyle 3 stroke:#1e90ff,stroke-width:4px
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:
graph TD A0(num: 0<br> val: -5)
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.length1 <= n <= 105-104 <= vals[i] <= 1040 <= edges.length <= min(n * (n - 1) / 2``, 105)edges[i].length == 20 <= ai, bi <= n - 1ai != bi0 <= k <= n - 1
Solution
Method 1 – Greedy with Priority Queue
Intuition
For each node, the best way to maximize the star sum is to select up to k neighbors with the largest positive values. We use a max-heap (priority queue) to efficiently pick the top k neighbors for each node.
Approach
- Build an adjacency list for the graph.
- For each node:
- Collect the values of all its neighbors.
- Use a max-heap to select up to
kneighbors with the highest values (only if positive). - Calculate the star sum as the node's value plus the sum of the selected neighbors' values.
- Track the maximum star sum found.
- Return the maximum star sum among all nodes.
Code
C++
class Solution {
public:
int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {
int n = vals.size(), ans = INT_MIN;
vector<vector<int>> g(n);
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
for (int i = 0; i < n; ++i) {
priority_queue<int> pq;
for (int v : g[i]) pq.push(vals[v]);
int sum = vals[i], cnt = 0;
while (!pq.empty() && cnt < k && pq.top() > 0) {
sum += pq.top(); pq.pop(); ++cnt;
}
ans = max(ans, sum);
}
return ans;
}
};
Go
func maxStarSum(vals []int, edges [][]int, k int) int {
n := len(vals)
g := make([][]int, n)
for _, e := range edges {
g[e[0]] = append(g[e[0]], e[1])
g[e[1]] = append(g[e[1]], e[0])
}
ans := vals[0]
for i := 0; i < n; i++ {
neighbors := []int{}
for _, v := range g[i] {
neighbors = append(neighbors, vals[v])
}
sort.Sort(sort.Reverse(sort.IntSlice(neighbors)))
sum := vals[i]
for j := 0; j < k && j < len(neighbors) && neighbors[j] > 0; j++ {
sum += neighbors[j]
}
if sum > ans {
ans = sum
}
}
return ans
}
Java
class Solution {
public int maxStarSum(int[] vals, int[][] edges, int k) {
int n = vals.length, ans = Integer.MIN_VALUE;
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) {
g.get(e[0]).add(e[1]);
g.get(e[1]).add(e[0]);
}
for (int i = 0; i < n; i++) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int v : g.get(i)) pq.offer(vals[v]);
int sum = vals[i], cnt = 0;
while (!pq.isEmpty() && cnt < k && pq.peek() > 0) {
sum += pq.poll(); cnt++;
}
ans = Math.max(ans, sum);
}
return ans;
}
}
Kotlin
class Solution {
fun maxStarSum(vals: IntArray, edges: Array<IntArray>, k: Int): Int {
val n = vals.size
val g = List(n) { mutableListOf<Int>() }
for (e in edges) {
g[e[0]].add(e[1])
g[e[1]].add(e[0])
}
var ans = vals[0]
for (i in 0 until n) {
val neighbors = g[i].map { vals[it] }.sortedDescending()
var sum = vals[i]
for (j in 0 until minOf(k, neighbors.size)) {
if (neighbors[j] > 0) sum += neighbors[j] else break
}
ans = maxOf(ans, sum)
}
return ans
}
}
Python
class Solution:
def maxStarSum(self, vals: list[int], edges: list[list[int]], k: int) -> int:
n = len(vals)
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
ans = vals[0]
for i in range(n):
neighbors = sorted([vals[v] for v in g[i]], reverse=True)
s = vals[i]
for j in range(min(k, len(neighbors))):
if neighbors[j] > 0:
s += neighbors[j]
else:
break
ans = max(ans, s)
return ans
Rust
impl Solution {
pub fn max_star_sum(vals: Vec<i32>, edges: Vec<Vec<i32>>, k: i32) -> i32 {
let n = vals.len();
let mut g = vec![vec![]; n];
for e in edges.iter() {
g[e[0] as usize].push(e[1] as usize);
g[e[1] as usize].push(e[0] as usize);
}
let mut ans = vals[0];
for i in 0..n {
let mut neighbors: Vec<i32> = g[i].iter().map(|&v| vals[v]).collect();
neighbors.sort_unstable_by(|a, b| b.cmp(a));
let mut sum = vals[i];
for j in 0..k.min(neighbors.len() as i32) as usize {
if neighbors[j] > 0 {
sum += neighbors[j];
} else {
break;
}
}
ans = ans.max(sum);
}
ans
}
}
TypeScript
class Solution {
maxStarSum(vals: number[], edges: number[][], k: number): number {
const n = vals.length;
const g: number[][] = Array.from({length: n}, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
let ans = vals[0];
for (let i = 0; i < n; i++) {
const neighbors = g[i].map(v => vals[v]).sort((a, b) => b - a);
let sum = vals[i];
for (let j = 0; j < Math.min(k, neighbors.length); j++) {
if (neighbors[j] > 0) sum += neighbors[j];
else break;
}
ans = Math.max(ans, sum);
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n + m + n k log k), where n is the number of nodes, m is the number of edges. For each node, we sort or heapify up to k neighbors. - 🧺 Space complexity:
O(n + m), for the adjacency list and temporary storage.