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

  1. Create an adjacency list, g, using defaultdict(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.

  2. For all edges (a, b), do the following:

    • If vals[b] is positive, append it to g[a] (connected nodes' values for a).
    • Conversely, if vals[a] is positive, append it to g[b].
  3. 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.

  4. Calculate the star sum for each node as the sum of its value, v, and the sum of at most k highest valued neighbors from the respective list in g. 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 its k highest connected nodes' values.

  5. Finally, the maxStarSum function returns the maximum star 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:

  1. 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).

  2. List: Python lists are used to store connected nodes' values and to sort these values in descending order.

Algorithm Steps:

  1. Creating Adjacency List (Undirected): The solution loops through each edge (a, b) in edges:

    • For node a, if vals[b] > 0, it appends this value to the list g[a].
    • For node b, similarly, if vals[a] > 0, it appends this value to the list g[b].

    This is because the graph is undirected, meaning either a or b can be the center of a star graph with the other being its neighbor.

  2. 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 to k neighbors, we're choosing the ones that maximize our sum.

  3. 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 the k highest neighboring node values from its list in g. This is done using a list comprehension:

    1return max(v + sum(g[i][:k]) for i, v in enumerate(vals))
    • g[i][:k] fetches at most the k largest values from node i's list of neighbors' values.
    • sum(g[i][:k]) calculates the sum of these up to k values.
    • v + sum(g[i][:k]) adds the node i's value to this sum to get the star sum for this particular node i 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 Evaluator

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

  1. Creating Adjacency List (Undirected): Our adjacency list g would be built as follows by iterating over the edges:

    1g[0] -> [2, 3, 4]    # Node 0 is connected to nodes 1, 2, 3 with positive values
    2g[1] -> [1, 5]       # Node 1 is connected to nodes 0 and 4
    3g[2] -> [1, 5]       # Node 2 is connected to nodes 0 and 4
    4g[3] -> [1]          # Node 3 is connected to node 0
    5g[4] -> [2, 3]       # Node 4 is connected to nodes 1 and 2
  2. Sorting Neighbors' Values: The next step is to sort each list of connected nodes' values in descending order:

    1g[0] -> [4, 3, 2]    # Sort 2, 3, 4 in descending order
    2g[1] -> [5, 1]       # Sort 1, 5 in descending order
    3g[2] -> [5, 1]       # Sort 1, 5 in descending order
    4g[3] -> [1]          # Already sorted since there's just one element
    5g[4] -> [3, 2]       # Sort 2, 3 in descending order
  3. 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:

    1For node 0: Star sum = 1 + (4+3) = 8 (Take the 2 highest values 4 and 3)
    2For 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)
    3For node 2: Star sum = 3 + (5) = 8 
    4For node 3: Star sum = 4 + (1) = 5 
    5For 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.

  4. Finding the Maximum Star Sum: The final step is to find the maximum star sum possible:

    1Maximum 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:

  1. Construction of the graph g: The for loop that iterates over the edges has a time complexity of O(E) where E is the number of edges because each edge is visited once.

  2. 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 take O(N log N) time per node to sort, where N is the number of nodes. However, typically the number of edges connected to a node (degree of a node) is much lower than N, so it will more often be O(D log D) where D is the average degree of a node.

  3. 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 to k elements from the sorted adjacency list. Since it iterates over all N nodes, this results in a O(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:

  1. Storing the graph g: The graph is stored using adjacency lists, which will require O(N + E) space: O(N) for storing N keys and O(E) for storing the list of neighbor values.

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

  3. 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 in O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does merge sort divide the problem into subproblems?


Recommended Readings