2497. Maximum Star Sum of a Graph
Problem Description
The problem describes an undirected graph with n
nodes numbered from 0
to n-1
. Each node has an associated value defined in the array vals
, where vals[i]
represents the value of the i
th node. Additionally, we are given a list of undirected edges defined in the array edges
. An edge connects two nodes, implying that the nodes are directly reachable from each other.
A star graph is a specific type of subgraph in which one central node is connected to some or all other nodes through edges, but those other nodes are not connected to each other. The star sum is the combined value of the nodes in this subgraph, including the central node and its neighbors.
The task is to find the maximum star sum possible by including at most k
edges in the star graph. In other words, what is the highest sum of node values we can achieve when we select a subset of the graph that forms a star graph, with the central node having up to k
neighbors.
Intuition
To find the maximum star sum, we should aim to include the nodes with the highest values adjacent to our chosen central node. Since the edges are undirected, we need to consider each node as a potential center of the star graph and calculate the maximum sum obtainable with it as the center.
The given solution follows these steps:
-
Create an adjacency list,
g
, usingdefaultdict(list)
from Python's collections module, to store the nodes (a
) and their corresponding connected nodes' values (vals[b]
) if their value is greater than zero. -
For all edges
(a, b)
, do the following:- If
vals[b]
is positive, append it tog[a]
(connected nodes' values fora
). - Conversely, if
vals[a]
is positive, append it tog[b]
.
- If
-
Sort the lists of connected nodes' values in descending order for each node in
g
. It ensures that the highest valued neighbor is considered first. -
Calculate the
star sum
for each node as the sum of its value,v
, and the sum of at mostk
highest valued neighbors from the respective list ing
. This is accomplished by iterating through all nodes enumerated along with their values (enumerate(vals)
) and computing the sum of a node's value and the total of itsk
highest connected nodes' values. -
Finally, the
maxStarSum
function returns the maximumstar sum
obtained from all possible center nodes.
The key to the solution is ensuring that the highest valued neighbors are included in the star graph to maximize the star sum, constrained by the limit of at most k
edges.
Learn more about Greedy, Graph, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution implements a simple but clever approach to maximize the star sum by leveraging a few common data structures and algorithms, as follows:
Data Structures Used:
-
Adjacency List: A defaultdict of lists is used to create an adjacency list
g
. It stores the values of connected nodes for each node (excluding values that are zero, as they do not contribute to the sum). -
List: Python lists are used to store connected nodes' values and to sort these values in descending order.
Algorithm Steps:
-
Creating Adjacency List (Undirected): The solution loops through each edge
(a, b)
inedges
:- For node
a
, ifvals[b] > 0
, it appends this value to the listg[a]
. - For node
b
, similarly, ifvals[a] > 0
, it appends this value to the listg[b]
.
This is because the graph is undirected, meaning either
a
orb
can be the center of a star graph with the other being its neighbor. - For node
-
Sorting Neighbors' Values: For each node's list of connected nodes in
g
, the values are sorted in reverse (descending) order. It ensures that when we choose up tok
neighbors, we're choosing the ones that maximize our sum. -
Calculating Star Sum: With the sorted lists for each potential center node, the star sum is calculated by taking the value of the current node
v
and adding the sum of thek
highest neighboring node values from its list ing
. This is done using a list comprehension:return max(v + sum(g[i][:k]) for i, v in enumerate(vals))
g[i][:k]
fetches at most thek
largest values from nodei
's list of neighbors' values.sum(g[i][:k])
calculates the sum of these up tok
values.v + sum(g[i][:k])
adds the nodei
's value to this sum to get the star sum for this particular nodei
as the center.max(...)
then finds the maximum star sum achievable from all potential center nodes.
Complexity Analysis:
- Time Complexity: O(V + E log E) where V is the number of nodes, and E is the number of edges. This is because E edges are iterated to build the adjacency list, and each neighbors list could potentially be sorted up to E times (in the worst case, where all edges are connected to a single node). Therefore, the bottleneck is the sorting operation.
- Space Complexity: O(E), as additional space is required to store neighbors' values for each node, and in the worst case, each node could hold values related to all other nodes.
Patterns Used:
- Greedy Algorithm: By sorting the neighbors' values in descending order and picking the top
k
elements, the solution uses a greedy approach where it always picks the local optimal choice (highest value) at each step to maximize the star sum in the end.
The solution effectively combines these data structures and algorithms to efficiently solve the maximum star sum problem while respecting the constraint of at most k
edges.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have a graph with 5 nodes (n=5
), numbered from 0 to 4. The values associated with each node are given by the array vals = [1, 2, 3, 4, 5]
, and we are allowed to include at most k=2
edges in our star graph to maximize the star sum. The edges are given by the array edges = [(0, 1), (0, 2), (0, 3), (1, 4), (2, 4)]
.
Step-by-Step Process:
-
Creating Adjacency List (Undirected): Our adjacency list
g
would be built as follows by iterating over the edges:g[0] -> [2, 3, 4] # Node 0 is connected to nodes 1, 2, 3 with positive values g[1] -> [1, 5] # Node 1 is connected to nodes 0 and 4 g[2] -> [1, 5] # Node 2 is connected to nodes 0 and 4 g[3] -> [1] # Node 3 is connected to node 0 g[4] -> [2, 3] # Node 4 is connected to nodes 1 and 2
-
Sorting Neighbors' Values: The next step is to sort each list of connected nodes' values in descending order:
g[0] -> [4, 3, 2] # Sort 2, 3, 4 in descending order g[1] -> [5, 1] # Sort 1, 5 in descending order g[2] -> [5, 1] # Sort 1, 5 in descending order g[3] -> [1] # Already sorted since there's just one element g[4] -> [3, 2] # Sort 2, 3 in descending order
-
Calculating Star Sum: Now, for each node, we will calculate the star sum by taking its value and adding the sum of its k highest valued neighbors:
For node 0: Star sum = 1 + (4+3) = 8 (Take the 2 highest values 4 and 3) For node 1: Star sum = 2 + (5) = 7 (Only 1 neighbor's value can be taken since k=2 and node 1's value has to be included) For node 2: Star sum = 3 + (5) = 8 For node 3: Star sum = 4 + (1) = 5 For node 4: Star sum = 5 + (3) = 8 (Same reasoning as node 1)
Note that we only include up to
k
neighbor's values, which is why even though node 0 has three neighbors, only the highest two (4 and 3) are included in the sum. -
Finding the Maximum Star Sum: The final step is to find the maximum star sum possible:
Maximum Star Sum = max(8, 7, 8, 5, 8) = 8
And so, the solution would return 8 as the maximum star sum possible by selecting a subset of the graph that forms a star graph with at most k
edges. This example clearly shows how the solution approach effectively uses a greedy method to maximize the star sum.
Solution Implementation
1from collections import defaultdict
2from typing import List
3
4class Solution:
5 def max_star_sum(self, values: List[int], edges: List[List[int]], k: int) -> int:
6 # Create a graph represented as an adjacency list
7 graph = defaultdict(list)
8
9 # Iterate over each edge and build an adjacency list for nodes with positive values
10 for node_a, node_b in edges:
11 if values[node_b] > 0:
12 graph[node_a].append(values[node_b])
13 if values[node_a] > 0:
14 graph[node_b].append(values[node_a])
15
16 # Sort the adjacency lists in descending order to prioritize larger values
17 for neighbors in graph.values():
18 neighbors.sort(reverse=True)
19
20 # Calculate the maximum star sum by adding the node's value to the
21 # sum of up to k highest values among its adjacent nodes
22 max_star_sum = max(value + sum(graph[node_index][:k]) for node_index, value in enumerate(values))
23
24 # Return the maximum star sum found
25 return max_star_sum
26
1class Solution {
2 // Function to calculate the maximum star sum
3 public int maxStarSum(int[] values, int[][] edges, int k) {
4 int numValues = values.length;
5
6 // Create a list of lists to represent the graph
7 List<Integer>[] graph = new List[numValues];
8 Arrays.setAll(graph, x -> new ArrayList<>());
9
10 // Building an adjacency list for each node containing values
11 for (int[] edge : edges) {
12 int from = edge[0], to = edge[1];
13
14 // Only add the positive values to the adjacency list
15 if (values[to] > 0) {
16 graph[from].add(values[to]);
17 }
18 if (values[from] > 0) {
19 graph[to].add(values[from]);
20 }
21 }
22
23 // Sort the adjacency lists in descending order
24 for (List<Integer> adjacentValues : graph) {
25 Collections.sort(adjacentValues, (a, b) -> b - a);
26 }
27
28 // Initialize the answer with the lowest possible value
29 int maxStarSum = Integer.MIN_VALUE;
30
31 // Iterate through each node to calculate the sum of the stars
32 for (int i = 0; i < numValues; ++i) {
33 int nodeValue = values[i];
34
35 // Add up the k highest values connected to the node
36 for (int j = 0; j < Math.min(graph[i].size(), k); ++j) {
37 nodeValue += graph[i].get(j);
38 }
39
40 // Update the answer with the maximum sum found so far
41 maxStarSum = Math.max(maxStarSum, nodeValue);
42 }
43
44 // Return the maximum star sum
45 return maxStarSum;
46 }
47}
48
1class Solution {
2public:
3 // Compute the maximum sum of star values with the center at each vertex considering 'k' arms
4 int maxStarSum(vector<int>& values, vector<vector<int>>& edges, int k) {
5 int numVertices = values.size(); // Number of vertices in the graph
6
7 // Adjacency list to hold the positive values of connected vertices
8 vector<vector<int>> adjacencyList(numVertices);
9
10 // Build the adjacency list with only positive values from connected vertices
11 for (auto& edge : edges) {
12 int vertexA = edge[0], vertexB = edge[1];
13 if (values[vertexB] > 0) adjacencyList[vertexA].emplace_back(values[vertexB]);
14 if (values[vertexA] > 0) adjacencyList[vertexB].emplace_back(values[vertexA]);
15 }
16
17 // Sort the adjacency list in descending order to prioritize larger values
18 for (auto& neighbors : adjacencyList) {
19 sort(neighbors.rbegin(), neighbors.rend());
20 }
21
22 // Variable to store the maximum star value found
23 int maxStarValue = INT_MIN;
24
25 // Iterate over each vertex to calculate the star value
26 for (int i = 0; i < numVertices; ++i) {
27 int starValue = values[i]; // Start with the value of the current vertex
28
29 // Add up to 'k' highest positive values from connected vertices
30 for (int j = 0; j < min(static_cast<int>(adjacencyList[i].size()), k); ++j) {
31 starValue += adjacencyList[i][j];
32 }
33
34 // Update the maximum star value if the current one is higher
35 maxStarValue = max(maxStarValue, starValue);
36 }
37
38 return maxStarValue; // Return the found maximum star value
39 }
40};
41
1// Define a VertexValue array type for clarity
2type VertexValueArray = number[];
3
4// Define an EdgeArray type for clarity
5type EdgeArray = number[][];
6
7// Function to compute the maximum sum of star values with the center at each vertex considering 'k' arms
8function maxStarSum(values: VertexValueArray, edges: EdgeArray, k: number): number {
9 const numVertices: number = values.length; // Number of vertices in the graph
10
11 // Adjacency list to hold the positive values of connected vertices
12 let adjacencyList: VertexValueArray[] = new Array(numVertices).fill(0).map(() => []);
13
14 // Build the adjacency list with only positive values from connected vertices
15 for (let edge of edges) {
16 let vertexA: number = edge[0], vertexB: number = edge[1];
17 if (values[vertexB] > 0) adjacencyList[vertexA].push(values[vertexB]);
18 if (values[vertexA] > 0) adjacencyList[vertexB].push(values[vertexA]);
19 }
20
21 // Sort the adjacency list in descending order to prioritize larger values
22 for (let neighbors of adjacencyList) {
23 neighbors.sort((a, b) => b - a);
24 }
25
26 // Variable to store the maximum star value found
27 let maxStarValue: number = Number.MIN_SAFE_INTEGER;
28
29 // Iterate over each vertex to calculate the star value
30 for (let i = 0; i < numVertices; ++i) {
31 let starValue: number = values[i]; // Start with the value of the current vertex
32
33 // Add up to 'k' highest positive values from connected vertices
34 for (let j = 0; j < Math.min(adjacencyList[i].length, k); ++j) {
35 starValue += adjacencyList[i][j];
36 }
37
38 // Update the maximum star value if the current one is higher
39 maxStarValue = Math.max(maxStarValue, starValue);
40 }
41
42 return maxStarValue; // Return the found maximum star value
43}
44
Time and Space Complexity
Time Complexity
The time complexity of the code is associated with several operations performed:
-
Construction of the graph
g
: Thefor
loop that iterates over theedges
has a time complexity ofO(E)
whereE
is the number of edges because each edge is visited once. -
Sorting the adjacency lists: Each adjacency list in graph
g
is sorted in reverse order. In the worst case, if all nodes are connected to all other nodes, it will takeO(N log N)
time per node to sort, whereN
is the number of nodes. However, typically the number of edges connected to a node (degree of a node) is much lower thanN
, so it will more often beO(D log D)
whereD
is the average degree of a node. -
Calculating the max star sum: The maximum star sum is computed in a single for loop that iterates over the nodes once. The complexity for this part is primarily from the summation operation which takes
O(k)
time for each node, as it sums up tok
elements from the sorted adjacency list. Since it iterates over allN
nodes, this results in aO(Nk)
time complexity.
The overall worst-case time complexity can be approximated by adding these components together: O(E + N log N + Nk)
.
However, the sorting step's time complexity will often be dominated by the number of edges (sorting smaller adjacency lists): O(E + D log D + Nk)
.
Space Complexity
The space complexity involves:
-
Storing the graph
g
: The graph is stored using adjacency lists, which will requireO(N + E)
space:O(N)
for storingN
keys andO(E)
for storing the list of neighbor values. -
Auxiliary space for sorting: Sorting the adjacency lists will require additional space which depends on the sorting algorithm used by Python's
.sort()
method (Timsort), but since in-place sorting is used, the impact on space complexity should be minimal. -
Storing sums: The space for storing the sums is not significant as it only stores the sums for each node which is
O(1)
per node resulting inO(N)
in total.
The overall space complexity is O(N + E)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!