Get started

Maximum Star Sum of a Graph — Medium Problem & Solution

An undirected graph has n nodes, and vals[i] is the value of node i.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Sorting, Heap, Graph
  • Asked at: Amazon, Google, Ola
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An undirected graph has n nodes, and vals[i] is the value of node i.

A star graph is a subgraph made of a centre node and zero or more of its direct neighbours; its star sum is the total of the values in it. Return the maximum star sum over all star graphs containing at most k edges.

Example 1

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: Centre node 3 with neighbours 4 and 1: `4 + 10 + 2`.

Example 2

Input: vals = [-5], edges = [], k = 0
Output: -5
Explanation: A lone centre is a valid star.

Example 3

Input: vals = [3,-1,-2], edges = [[0,1],[0,2]], k = 2
Output: 3
Explanation: Both neighbours are negative, so take neither.

Constraints

  • n == vals.length
  • 1 <= n <= 10^5
  • -10^4 <= vals[i] <= 10^4
  • 0 <= edges.length <= min(n * (n - 1) / 2, 10^5)
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • edges[i][0] != edges[i][1]
  • 0 <= k <= n - 1

How to solve Maximum Star Sum of a Graph

The centres are independent, so evaluate each one. For a given centre the choice is greedy: adding a neighbour changes the sum by exactly that neighbour's value, so take the largest positive ones up to the budget.

Approach

  1. Collect, for every node, the values of its neighbours.
  2. For each centre, keep only the positive neighbour values and sort them descending.
  3. Add the first min(k, count) of them to the centre's own value.
  4. Return the largest total.

Why it works

Each edge's contribution is independent of the others, so no interaction can make a negative neighbour worth taking — the greedy choice is exactly optimal. Note the centre's own value is always included even when negative: a star must have a centre, which is why an all-negative graph answers with its largest single value rather than zero.

Complexity

  • Time — O(n + m + Σ deg · log deg)
  • Space — O(n + m)

Pitfalls

  • The centre's value is mandatory; only the neighbours are optional.
  • Taking a negative neighbour to fill the budget lowers the sum — k is a cap, not a quota.
  • k may be 0, which leaves only the isolated centres.

Reference solution

Python

from typing import List

def maxStarSum(vals: List[int], edges: List[List[int]], k: int) -> int:
    n = len(vals)
    nb = [[] for _ in range(n)]
    for u, v in edges:
        nb[u].append(vals[v])
        nb[v].append(vals[u])
    best = None
    for i in range(n):
        pos = sorted((v for v in nb[i] if v > 0), reverse=True)
        total = vals[i] + sum(pos[:k])
        if best is None or total > best:
            best = total
    return best

JavaScript

var maxStarSum = function(vals, edges, k) {
    var n = vals.length, i;
    var nb = [];
    for (i = 0; i < n; i++) nb.push([]);
    for (i = 0; i < edges.length; i++) {
        nb[edges[i][0]].push(vals[edges[i][1]]);
        nb[edges[i][1]].push(vals[edges[i][0]]);
    }
    var best = -2000000000;
    for (i = 0; i < n; i++) {
        var pos = nb[i].filter(function(v) { return v > 0; });
        pos.sort(function(a, b) { return b - a; });
        var sum = vals[i];
        var take = k < pos.length ? k : pos.length;
        for (var t = 0; t < take; t++) sum += pos[t];
        if (sum > best) best = sum;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue