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 Score of a Node Sequence

Number: 2353

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an undirected graph with n nodes (numbered from 0 to n–1), each node has an associated score provided in the array scores. A list of edges specifies the connections between nodes. A valid node sequence of length 4 is one in which every pair of adjacent nodes is connected by an edge and no node appears more than once. The task is to find the valid sequence with the maximum total score (i.e. the sum of scores of nodes in the sequence). If no such sequence exists, return –1.

Key Insights

  • Since the sequence must be of length 4, a natural candidate structure is: a, b, c, d where b and c are connected by an edge and a is connected to b while d is connected to c.
  • For each node, keep track of the top (up to) three neighbors (based on their scores) that can be candidates to form the sequence endpoints.
  • Iterate over each edge and treat it as the middle edge (between b and c). Then, try to attach the best candidate neighbors from b (for a) and from c (for d), ensuring all four nodes are distinct.
  • The candidate lists for each node are maintained in descending order of scores to quickly obtain high-scoring endpoints.
  • Carefully check for distinctness among the four nodes when combining candidate endpoints with the central edge.

Space and Time Complexity

Time Complexity: O(m) where m is the number of edges, since for each edge we only try a constant number of candidate extensions. Space Complexity: O(n + m) for the graph representation and candidate lists.

Solution

We precompute for each node a sorted list (by score) of up to three neighboring nodes. Then, for every edge (u, v) in the graph, we consider it as the middle edge of a potential sequence. For node u, choose a candidate neighbor a (from its candidate list) that is not v. Similarly, for node v, choose a candidate neighbor d (from its candidate list) that is not u and not equal to a. Compute the total score as scores[a] + scores[u] + scores[v] + scores[d]. Update the maximum score encountered. Edge cases such as missing candidates or duplicate nodes in the sequence are handled by these checks.

Code Solutions

# Python solution with detailed comments

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        from collections import defaultdict
        
        n = len(scores)
        # Graph adjacency list to hold the original neighbors
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        # For each node, maintain the top three neighbors with highest scores.
        top_neighbors = [[] for _ in range(n)]
        for node in range(n):
            # Sort each neighbor list by score in descending order, only keep top 3
            neighbors = sorted(graph[node], key=lambda x: scores[x], reverse=True)
            top_neighbors[node] = neighbors[:3]
        
        max_score = -1
        # Traverse each edge and consider it as the middle edge: (u, v)
        for u, v in edges:
            # Try both orders: u as b and v as c, and vice versa.
            for b, c in [(u, v), (v, u)]:
                # Try all candidate nodes for 'a' from b's top neighbors; skip if candidate is c.
                for a in top_neighbors[b]:
                    if a == c:
                        continue
                    # Try all candidate nodes for 'd' from c's top neighbors; ensure d is distinct from b and a.
                    for d in top_neighbors[c]:
                        if d == b or d == a:
                            continue
                        curr_score = scores[a] + scores[b] + scores[c] + scores[d]
                        max_score = max(max_score, curr_score)
                        # Since sorted, break early if possible (optional optimization)
                # End of candidate exploration for this ordering.
        return max_score
← Back to All Questions