We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Star Sum of a Graph

Difficulty: Medium

Problem Description

Given an undirected graph consisting of n nodes and a 0-indexed integer array vals where vals[i] denotes the value of the i-th node, along with a 2D integer array edges representing the connections between nodes, determine the maximum star sum of a star graph containing at most k edges. A star graph is defined as a subgraph where there is a central node connected to a subset of its neighbors.

Key Insights

  • A star graph is centered around one node and includes its neighbors.
  • The star sum is calculated by adding the values of the central node and its neighbors.
  • The challenge is to maximize the star sum while adhering to the limit of k edges.
  • It is important to consider only neighbors with positive values since including negative values would decrease the star sum.

Space and Time Complexity

Time Complexity: O(n + m log m), where n is the number of nodes and m is the number of edges (for sorting).
Space Complexity: O(n + m), for storing the adjacency list and neighbor values.

Solution

To solve the problem, we follow these steps:

  1. Create an adjacency list to represent the graph using the given edges.
  2. For each node, collect the values of its neighbors.
  3. Sort the neighbor values in descending order to prioritize the highest values.
  4. Calculate the star sum for each node by adding its value to the values of its top k neighbors (considering only positive values).
  5. Return the maximum star sum found across all nodes.

Code Solutions

def maxStarSum(vals, edges, k):
    from collections import defaultdict
    import heapq

    # Create adjacency list
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(vals[b])
        graph[b].append(vals[a])
    
    max_sum = float('-inf')

    # Calculate star sums
    for i in range(len(vals)):
        neighbor_values = graph[i]
        # Sort neighbors' values in descending order
        neighbor_values.sort(reverse=True)
        
        # Calculate star sum for this node
        current_sum = vals[i]
        for j in range(min(k, len(neighbor_values))):
            if neighbor_values[j] > 0:  # Only consider positive values
                current_sum += neighbor_values[j]
            else:
                break  # No need to add negative values
        
        max_sum = max(max_sum, current_sum)

    return max_sum
← Back to All Questions