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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Star Sum of a Graph

Number: 2590

Difficulty: Medium

Paid? No

Companies: Akuna Capital, Google, Amazon

Problem Description

Given an undirected graph where each node has an associated value, the goal is to select a star graph (a central node with a subset of its neighbors) that maximizes the sum of node values. The star graph may include at most k edges. Essentially, for each potential center node, you may choose up to k of its neighbors (only if they add positive contribution) to maximize the total sum.

Key Insights

  • Each star graph has a center node; start the sum with the center's value.
  • The contribution of a neighbor is only beneficial if its value is positive.
  • For each node, sort its neighbors by value in descending order to consider the highest contributions first.
  • Because the graph is undirected, every edge allows both endpoints to potentially be the center of a star.

Space and Time Complexity

Time Complexity: O(n log n + m), where n is the number of nodes and m is the number of edges. The dominant cost comes from creating the adjacency list and sorting the neighbor lists for each node. Space Complexity: O(n + m) due to storing the graph in an adjacency list format.

Solution

The solution follows these steps:

  1. Build an adjacency list where each node points to a list of its neighbors' values.
  2. For each node (considered as the potential star center), sort its neighbor list in descending order.
  3. Start with the center node's value, and add up to k neighbor values if they are positive.
  4. Track the maximum result obtained over all centers. This greedy approach ensures that for every node, only the most beneficial edges (neighbors with positive values) are selected.

Code Solutions

def maxStarSum(vals, edges, k):
    from collections import defaultdict
    # Build the adjacency list: node -> list of neighbor values.
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(vals[v])
        graph[v].append(vals[u])
    
    max_sum = float("-inf")
    
    # Evaluate each node as the center of the star graph.
    for i in range(len(vals)):
        current_sum = vals[i]
        neighbors = graph[i]
        # Sort neighbor contributions in descending order.
        neighbors.sort(reverse=True)
        count = 0
        
        # Include up to k positive neighbor contributions.
        for value in neighbors:
            if count < k and value > 0:
                current_sum += value
                count += 1
            else:
                break
        max_sum = max(max_sum, current_sum)
    
    return max_sum

# Example usage:
vals = [1,2,3,4,10,-10,-20]
edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]]
k = 2
print(maxStarSum(vals, edges, k))
← Back to All Questions