Maximum Star Sum of a Graph

Medium
934.

Maximum Star Sum of a Graph

MediumArrayGraphGreedySortingHeap (Priority Queue)AmazonGoogleOla

Maximum Star Sum of a Graph is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Ola interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} vals
 * @param {number[][]} edges
 * @param {number} k
 * @return {number}
 */
var maxStarSum = function(vals, edges, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Star Sum of a Graph — Solution in Python, Java & C++

Maximum Star Sum of a Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Star Sum of a Graph is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Ola interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Graph, Heap
  • 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

Hints for Maximum Star Sum of a Graph

  1. Hint 1

    Try every node as the centre.

  2. Hint 2

    For a fixed centre, which neighbours would you add?

  3. Hint 3

    Only the positive ones, largest first, and at most k of them.

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

Java

public static int maxStarSum(int[] vals, int[][] edges, int k) {
    int n = vals.length;
    List<List<Integer>> nb = new ArrayList<>();
    for (int i = 0; i < n; i++) nb.add(new ArrayList<>());
    for (int[] e : edges) {
        nb.get(e[0]).add(vals[e[1]]);
        nb.get(e[1]).add(vals[e[0]]);
    }
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        List<Integer> pos = new ArrayList<>();
        for (int v : nb.get(i)) if (v > 0) pos.add(v);
        pos.sort(Comparator.reverseOrder());
        int sum = vals[i];
        int take = Math.min(k, pos.size());
        for (int t = 0; t < take; t++) sum += pos.get(t);
        best = Math.max(best, sum);
    }
    return best;
}

C++

int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {
    int n = (int) vals.size();
    vector<vector<int>> nb(n);
    for (auto& e : edges) {
        nb[e[0]].push_back(vals[e[1]]);
        nb[e[1]].push_back(vals[e[0]]);
    }
    int best = INT_MIN;
    for (int i = 0; i < n; i++) {
        vector<int> pos;
        for (int v : nb[i]) if (v > 0) pos.push_back(v);
        sort(pos.begin(), pos.end(), greater<int>());
        int sum = vals[i];
        int take = min((int) pos.size(), k);
        for (int t = 0; t < take; t++) sum += pos[t];
        best = max(best, sum);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms