Maximum Star Sum of a Graph

Reported in interviews at Akuna Capital

Problem statement

You are given an undirected graph with $n$ nodes labeled $0 \dots n-1$. Node $i$ has value $\mathrm{vals}[i]$ (values may be negative). You are also given a list $\mathrm{edges}$, where $\mathrm{edges}[j] = [u, v]$ is an undirected edge, and an integer $k$.

A star graph is a subgraph made of one node (the center) together with at most $k$ of its direct neighbors. The star sum is the sum of the values of all nodes in the star (the center plus the chosen neighbors).

Return the maximum star sum over every choice of center and neighbors.

Constraints:

  • $1 \le n \le 10^5$
  • $\mathrm{vals}[i]$ may be negative or positive
  • $0 \le k \le n - 1$

Examples:

  • $\mathrm{vals} = [1,2,3,4,10,-10,-20]$, $\mathrm{edges} = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]$, $k = 2 \to 16$. Center node $3$ (value $4$) plus its two best neighbors, node $4$ ($10$) and node $1$ ($2$): $4 + 10 + 2 = 16$.
  • $\mathrm{vals} = [-5]$, $\mathrm{edges} = []$, $k = 0 \to -5$. The only star is the lone node.
Show hint

If you fix the centre first, do the choices of which neighbours to include affect each other at all?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems