Maximum Star Sum of a Graph

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
 val: 1)
    A1(num: 1
 val: 2)
    A2(num: 2
 val: 3)
    A3(num: 3
 val: 4)
    A4(num: 4
 val: 10)
    A5(num: 5
 val: -10)
    A6(num: 6
 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

1
2
3
4
5
6
7


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
 val: -5)

1
2
3
4
5
6


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.length
1 <= n <= 105
-104 <= vals[i] <= 104
0 <= edges.length <= min(n * (n - 1) / 2``, 105)
edges[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
0 <= 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 k neighbors 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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.

Problem#

Examples#

Solution#

Method 1 – Greedy with Priority Queue#

Intuition#

Approach#

Code#

Complexity#