Skip to main content
Talentd

Maximum Star Sum of a Graph - Solution & Explanation

MediumArrayGreedyGraphSorting15 min readAsked at: Amazon, Google, Akuna Capital
Practice this problem

Problem Statement

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.

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:

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

Approach Overview

Problem Overview: You are given a graph where each node has a value. A star consists of a center node and up to k of its neighbors. The goal is to choose neighbors that maximize the total star sum (center value + selected neighbor values). You must evaluate every node as a potential center and return the maximum possible sum.

Approach 1: Sorting and Two-Pointer Technique (O(E log E) time, O(E) space)

Build an adjacency list for the graph, then collect the values of all neighbors for each node. Sort the neighbor values in descending order so the largest contributors appear first. From the sorted list, greedily pick up to k positive values and add them to the center node’s value. A two-pointer style scan works well here: start from the largest values and stop when either k neighbors are selected or the values become non‑positive. Sorting ensures you always consider the highest-value neighbors first, which maximizes the star sum.

This approach works because negative neighbors never increase the sum, so they are ignored after sorting. The algorithm iterates through each node, sorts its neighbor values, and accumulates the best k. Time complexity is O(E log E) in the worst case due to sorting neighbor lists, while space complexity is O(E) for the adjacency representation. This method relies heavily on Sorting and greedy selection, making it straightforward to implement in most languages.

Approach 2: Hash Map for Complement Lookup (O(E log k) time, O(E) space)

Use a hash map to build the adjacency list so each node quickly maps to its neighbors. While iterating through edges, track neighbor contributions and maintain only the best k candidates for each center. A bounded structure such as a small heap or ordered container keeps the top positive values without sorting the entire list. The hash map ensures constant-time access to neighbor sets, which is helpful when the graph is large or sparsely connected.

The key idea is to limit storage to the top k positive neighbor values per node. Instead of sorting every neighbor list, maintain a structure that discards smaller values once the size exceeds k. This reduces unnecessary comparisons and keeps the runtime closer to O(E log k). The approach combines Graph traversal with hash-based adjacency storage and optional Heap (Priority Queue) optimization.

Recommended for interviews: The sorting-based greedy approach is the most commonly expected solution. It clearly demonstrates understanding of graph adjacency lists and greedy selection of the largest contributors. Mentioning the optimized variant that keeps only the top k values (using a heap or bounded container) shows stronger algorithmic thinking and awareness of performance tradeoffs.

Approach 1: Approach 1: Sorting and Two-Pointer Technique

This approach involves sorting the dataset and then using the two-pointer technique to find the desired result. Sorting helps to systematically approach the dataset, and using two pointers minimizes the need for nested loops, making the solution efficient.

The C implementation sorts the array using quick sort and then applies the two-pointer technique to identify pairs whose sum matches the target. The qsort function is used for sorting. Two pointers, left and right, start at the beginning and end of the array, respectively, adjusting based on the sum comparison with the target.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting and O(n) for the two-pointer traversal, resulting in a combined O(n log n).
Space Complexity: O(1) as no extra space is used beyond input and sorting operations.

Try this approach in the editor →

Approach 2: Approach 2: Hash Map for Complement Lookup

Another effective approach uses a hash map to track complements of numbers as you iterate through the dataset. This technique allows for constant time lookup of any complement needed to form the target sum, drastically improving efficiency over conventional looping methods.

In C, a hash table is implemented using an array of linked lists for handling hash collisions. As elements from the array are processed, complements necessary to achieve the target sum are stored and checked within the hash table for pairs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for linear iteration and constant-time hash operations, assuming a good distribution.
Space Complexity: O(n) for storing elements in the hash table.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Two-Pointer Technique

Time Complexity: O(n log n) due to sorting and O(n) for the two-pointer traversal, resulting in a combined O(n log n).
Space Complexity: O(1) as no extra space is used beyond input and sorting operations.

Approach 2: Hash Map for Complement Lookup

Time Complexity: O(n) for linear iteration and constant-time hash operations, assuming a good distribution.
Space Complexity: O(n) for storing elements in the hash table.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Two-Pointer TechniqueO(E log E)O(E)Simple implementation when neighbor lists are small or sorting overhead is acceptable
Hash Map with Top-K TrackingO(E log k)O(E)Large graphs where maintaining only the top k neighbors avoids repeated sorting

Video Solution

Maximum Star Sum of a Graph || leetcode Biweekly 93 || Leetcode Medium • BinaryMagic • 1,198 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Star Sum of a Graph easy or hard?
Maximum Star Sum of a Graph is classified as a Medium difficulty problem. The main challenge is recognizing that only the top k positive neighbors matter and implementing an efficient way to select them using sorting or a heap.
Maximum Star Sum of a Graph Python/Java solution
A Python or Java solution builds an adjacency list, gathers neighbor values for each node, sorts them in descending order, and sums the top k positive values with the center node. The same logic translates directly to C++, JavaScript, and other languages using built‑in sorting utilities.
How to solve Maximum Star Sum of a Graph in O(n)?
Strict O(n) is difficult because neighbor values must be compared to find the top contributors. A near‑linear approach maintains a small heap of size k for each node while processing edges. This avoids full sorting and keeps the complexity closer to O(E log k), which performs well when k is small.
What is the best approach for Maximum Star Sum of a Graph?
The most practical solution builds an adjacency list and sorts neighbor values for each node. After sorting in descending order, add up to k positive neighbor values to the center node’s value. This greedy method ensures the largest contributions are selected first and runs in about O(E log E) time.
Is Maximum Star Sum of a Graph asked at Google/Amazon/Meta?
Graph problems involving greedy selection and neighbor aggregation appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that combine adjacency lists with heaps or sorting are common because they test both graph representation and optimization skills.
What data structure is used in Maximum Star Sum of a Graph?
The solution typically uses an adjacency list to represent the graph, along with arrays or lists for node values. Many optimized implementations also use a heap (priority queue) to maintain the top k neighbor values efficiently.
What is the time complexity of Maximum Star Sum of a Graph?
The common greedy approach using sorted neighbor lists runs in O(E log E) time, where E is the number of edges. Each node evaluates its neighbors after sorting their values. With an optimization that keeps only the top k neighbors using a heap, the complexity improves to roughly O(E log k).

Ready to solve this problem?

Practice Maximum Star Sum of a Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Center of Star Graph

Next

Number Of Ways To Reconstruct A Tree