Maximum star sum of a graph

Array Greedy Graph Theory Sorting Heap (Priority Queue)

42.0% acceptance

Feb 25, 2026

451

You are given n nodes (0-indexed) with values vals[i] and edges. A star graph centered at node c with at most k neighbors. Star sum = vals[c] + sum of top-k positive neighbor vals. Return maximum star sum.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_star_sum(vals: Vec<i32>, edges: Vec<Vec<i32>>, k: i32) -> i32 {
    let n = vals.len();
    let k = k as usize;
    let mut neighbors: Vec<Vec<i32>> = vec![vec![]; n];
    for e in &edges {
      let (a, b) = (e[0] as usize, e[1] as usize);
      if vals[b] > 0 { neighbors[a].push(vals[b]); }
      if vals[a] > 0 { neighbors[b].push(vals[a]); }
    }
    (0..n).map(|i| {
      neighbors[i].sort_unstable_by(|a, b| b.cmp(a));
      vals[i] + neighbors[i].iter().take(k).sum::<i32>()
    }).max().unwrap()
  }
}