# Maximum Star Sum of a Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-star-sum-of-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/maximum-star-sum-of-a-graph
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue), Graph
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## 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.

![](https://assets.glich.co/dsa/maximum-star-sum-of-a-graph/image0.png) 

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._

**Example 1:**

![](https://assets.glich.co/dsa/maximum-star-sum-of-a-graph/image1.png) 

**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:**

**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`

# Approaches
## Iteration with Sorting
This approach iterates through each node, considering it as a potential center of a star graph. For each potential center, it calculates the maximum possible star sum by adding the values of its `k` most valuable neighbors. To find these neighbors, it collects the values of all neighbors, filters for positive ones, sorts them in descending order, and picks the top `k`. The overall maximum sum found across all possible centers is the answer.
**Time:** O(E + Σ(deg(i) * log(deg(i)))) over all nodes `i`. A simpler upper bound is `O(E * log N)`, where `E` is the number of edges and `N` is the number of nodes. Building the adjacency list takes `O(E)`. For each node `i`, we sort its neighbors, taking `O(deg(i) * log(deg(i)))`. The sum of degrees `Σdeg(i)` is `2*E`. · **Space:** O(E + N), where `E` is the number of edges and `N` is the number of nodes. This is for the adjacency list and the temporary list for sorting neighbor values (which can be up to size `N-1` in the worst case).
**Pros:** Relatively straightforward to understand and implement.; Correctly solves the problem.
**Cons:** Sorting all positive neighbors for each node can be inefficient, especially if `k` is small compared to the node's degree. We only need the top `k` elements, not a fully sorted list.
### Explanation
The core idea is to check every node as a potential center for the star graph.

First, we need an efficient way to access the neighbors of any given node. An adjacency list is a suitable data structure for this, which can be built by iterating through the `edges` array once.

We initialize a variable `maxSum` to the smallest possible integer value to keep track of the maximum star sum found so far. 

Then, we loop through each node `i` from `0` to `n-1`.
- For each node `i`, we calculate the potential star sum with `i` as the center. The sum starts with `vals[i]`.
- We gather the values of all neighbors of `i`. We are only interested in neighbors that increase the total sum, so we only consider neighbors with positive values.
- We store these positive neighbor values in a list.
- To pick the best `k` neighbors, we sort this list of positive values in descending order.
- We then iterate up to `k` times (or until we run out of positive neighbors) and add the values from the sorted list to our current sum.
- After calculating the maximum possible sum for the center `i`, we update `maxSum = max(maxSum, currentSum)`.

After checking all nodes as potential centers, `maxSum` will hold the final answer.

```java
import java.util.*;

class Solution {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int currentSum = vals[i];
            List<Integer> neighborValues = new ArrayList<>();
            for (int neighbor : adj.get(i)) {
                if (vals[neighbor] > 0) {
                    neighborValues.add(vals[neighbor]);
                }
            }

            Collections.sort(neighborValues, Collections.reverseOrder());

            for (int j = 0; j < Math.min(k, neighborValues.size()); j++) {
                currentSum += neighborValues.get(j);
            }
            
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}
```
### Algorithm
- Create an adjacency list to represent the graph from the `edges` array.
- Initialize a variable `maxSum` to `Integer.MIN_VALUE`.
- Iterate through each node `i` from `0` to `n-1`, treating it as the center of a star graph.
- For each center `i`, initialize `currentSum = vals[i]`.
- Create a list to store the values of its neighbors.
- Iterate through the neighbors of `i` using the adjacency list. If a neighbor's value is positive, add it to the list.
- Sort the list of positive neighbor values in descending order.
- Add the top `k` values (or fewer if the list is smaller than `k`) from the sorted list to `currentSum`.
- Update `maxSum` with the maximum of `maxSum` and `currentSum`.
- After iterating through all nodes, return `maxSum`.

## Iteration with Min-Heap
This approach improves upon the sorting method. Instead of sorting all positive neighbor values for each center node, it uses a min-heap (Priority Queue) of size `k` to efficiently find the `k` largest positive neighbor values. This avoids the cost of a full sort, making it more efficient, especially when a node has many neighbors but `k` is small.
**Time:** O(E * log k). Building the adjacency list is `O(E)`. For each node `i`, we iterate through its `deg(i)` neighbors. Each heap operation takes `O(log k)` time. The total time for the main loop is `Σ(deg(i) * log k)` over all `i`, which is `2*E*log(k)`. · **Space:** O(E + k). `O(E)` for the adjacency list and `O(k)` for the priority queue used for each node.
**Pros:** More efficient than the sorting approach, especially when `k` is small.; It's an optimal approach for the given constraints.
**Cons:** Slightly more complex to implement due to the use of a priority queue.
### Explanation
Similar to the first approach, we iterate through each node `i` as a potential center. The graph representation is also an adjacency list.

The key difference lies in how we select the top `k` neighbors. Instead of collecting all positive neighbor values and sorting them, we use a min-heap of a fixed maximum size `k`.

For each center node `i`, we initialize its star sum `currentSum = vals[i]`.
- We create a min-heap (in Java, `PriorityQueue`).
- We iterate through the neighbors of `i`. For each neighbor `j` with a positive value `vals[j]`:
  - We add `vals[j]` to the min-heap.
  - If the size of the heap exceeds `k`, we remove the smallest element (the root of the min-heap). This ensures the heap always contains the `k` largest values seen so far for the current center's neighbors.
- After checking all neighbors of `i`, the heap contains up to `k` of the largest positive neighbor values.
- We sum up all the values in the heap and add them to `currentSum`.
- We then update the global `maxSum` with this `currentSum` if it's larger.

This process is repeated for all nodes, and the final `maxSum` is returned.

```java
import java.util.*;

class Solution {
    public int maxStarSum(int[] vals, int[][] edges, int k) {
        int n = vals.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            int currentSum = vals[i];
            // Min-heap to store the k largest positive neighbor values
            PriorityQueue<Integer> pq = new PriorityQueue<>();

            for (int neighbor : adj.get(i)) {
                if (vals[neighbor] > 0) {
                    pq.add(vals[neighbor]);
                    if (pq.size() > k) {
                        pq.poll();
                    }
                }
            }

            while (!pq.isEmpty()) {
                currentSum += pq.poll();
            }
            
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}
```
### Algorithm
- Create an adjacency list to represent the graph.
- Initialize `maxSum` to `Integer.MIN_VALUE`.
- Iterate through each node `i` from `0` to `n-1` as a potential center.
- For each center `i`, initialize `currentSum = vals[i]`.
- Create a min-heap (PriorityQueue) to keep track of the largest neighbor values.
- Iterate through the neighbors of `i`. For each neighbor `j` with `vals[j] > 0`:
  - Add `vals[j]` to the heap.
  - If the heap's size is greater than `k`, remove the smallest element from the heap (`poll()`).
- After iterating through all neighbors, sum the elements remaining in the heap and add them to `currentSum`.
- Update `maxSum = max(maxSum, currentSum)`.
- After checking all nodes, return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maxStarSum(int[] vals, int[][] edges, int k) {
    int n = vals.length;
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, key->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      if (vals[b] > 0) {
        g[a].add(vals[b]);
      }
      if (vals[a] > 0) {
        g[b].add(vals[a]);
      }
    }
    for (var e : g) {
      Collections.sort(e, (a, b)->b - a);
    }
    int ans = Integer.MIN_VALUE;
    for (int i = 0; i < n; ++i) {
      int v = vals[i];
      for (int j = 0; j < Math.min(g[i].size(), k); ++j) {
        v += g[i].get(j);
      }
      ans = Math.max(ans, v);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxStarSum(vector<int> &vals, vector<vector<int>> &edges, int k) {
    int n = vals.size();
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      if (vals[b] > 0)
        g[a].emplace_back(vals[b]);
      if (vals[a] > 0)
        g[b].emplace_back(vals[a]);
    }
    for (auto &e : g)
      sort(e.rbegin(), e.rend());
    int ans = INT_MIN;
    for (int i = 0; i < n; ++i) {
      int v = vals[i];
      for (int j = 0; j < min((int)g[i].size(), k); ++j)
        v += g[i][j];
      ans = max(ans, v);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int: g = defaultdict(list) for a, b in edges: if vals[b] > 0: g[a]. append(vals[b]) if vals[a] > 0: g[b]. append(vals[a]) for bs in g . values(): bs . sort(reverse=True) return max(v + sum(g[i][: k]) for i, v in enumerate(vals))

```