LeetCode 2242 - Maximum Score of a Node Sequence

Difficulty: 🔴 Hard
Topics: Array, Graph Theory, Sorting, Enumeration

Solution

Problem Understanding

The problem gives us an undirected graph with n nodes. Each node has a score, and the graph edges define which nodes are directly connected. We must find a valid sequence of exactly four distinct nodes such that every adjacent pair in the sequence has an edge between them.

A valid sequence looks like this:

a - b - c - d

This means:

(a, b) must be an edge
(b, c) must be an edge
(c, d) must be an edge
all four nodes must be distinct

The score of the sequence is:

scores[a] + scores[b] + scores[c] + scores[d]

We must return the maximum possible score among all valid sequences of length 4. If no such sequence exists, we return -1.

The graph is undirected, so if [u, v] exists in edges, then travel is allowed both from u to v and from v to u.

The constraints are extremely important here:

n can be up to 5 * 10^4
edges.length can also be up to 5 * 10^4

These limits immediately rule out brute force enumeration over all quadruples of nodes. Enumerating all possible 4-node sequences would be far too expensive.

The graph is relatively sparse because the number of edges is only up to 5 * 10^4, not n^2. This hints that an edge-based strategy will likely be efficient.

Several edge cases are important:

The graph may not contain any path of length 3, so the answer could be -1.
Multiple high-scoring nodes may overlap, requiring careful distinctness checks.
Some nodes may have very large degree counts, so iterating over all neighbor combinations naively can become expensive.
The best sequence may not be unique.
Because scores can be up to 10^8, the total sequence score can become large, but it still safely fits within 32-bit signed integer range because 4 * 10^8 is below 2^31 - 1.

Approaches

Brute Force Approach

A straightforward brute force solution would enumerate every possible ordered sequence of four distinct nodes:

(a, b, c, d)

For each sequence, we would check:

whether all nodes are distinct
whether edges (a,b), (b,c), and (c,d) exist

If valid, we compute the total score and track the maximum.

This approach is correct because it explicitly checks every possible candidate sequence.

However, the complexity is disastrous. There are up to:

O(n^4)

possible quadruples. With n = 5 * 10^4, this is completely infeasible.

Even if edge lookups are optimized using adjacency sets, the enumeration itself is impossible within time limits.

Optimal Approach

The key observation is that every valid sequence has a middle edge:

a - b - c - d
      ^
    middle edge

If we fix the middle edge (b, c), then:

a must be a neighbor of b
d must be a neighbor of c
all four nodes must be distinct

Instead of exploring every quadruple, we iterate over every edge as the center of the sequence.

Now the problem becomes:

For each edge (b, c), find the best neighbor of b and the best neighbor of c that do not violate distinctness.

A further optimization makes the solution efficient:

For every node, we only keep its top 3 highest-scoring neighbors.

Why is this enough?

A valid sequence only needs one neighbor on each side. Even if some top neighbors conflict because of duplicate nodes, having the best 3 neighbors guarantees we still have enough candidates to test all valid combinations.

This dramatically reduces the search space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Enumerates all possible 4-node sequences
Optimal	O(E)	O(E)	Uses top neighbors and edge-centered enumeration

Here, E represents the number of edges.

Algorithm Walkthrough

Build an adjacency structure for the graph.

For each node, we store its neighbors. However, instead of keeping all neighbors indefinitely, we eventually only care about the top 3 neighbors with the highest scores. 2. For every edge [u, v], add:

v as a candidate neighbor of u
u as a candidate neighbor of v

Each candidate is evaluated based on the neighbor's score. 3. For each node, sort its neighbor list in descending order by neighbor score.

Then keep only the top 3 neighbors.

This optimization is critical because it limits future enumeration work to a tiny constant size. 4. Initialize the answer as -1.

If we never discover a valid sequence, this value will remain unchanged. 5. Iterate through every edge (b, c).

Treat this edge as the middle connection in:

a - b - c - d

For every candidate neighbor a of b and every candidate neighbor d of c:

ensure all four nodes are distinct
specifically:
a != c
d != b
a != d

If the sequence is valid, compute:

scores[a] + scores[b] + scores[c] + scores[d]

Update the maximum answer. 8. After all edges are processed, return the maximum score found.

Why it works

Every valid sequence must contain some middle edge (b, c). By iterating through every edge, we guarantee that every possible valid sequence is considered.

For each node, keeping only the top 3 neighbors is sufficient because at most a few candidates become invalid due to overlap constraints. If a valid optimal sequence exists, one of those top candidates will still remain available.

Therefore, the algorithm explores all relevant high-value combinations while avoiding unnecessary enumeration.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)

        # Store neighbors for each node
        neighbors = [[] for _ in range(n)]

        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)

        # Keep only top 3 neighbors by score
        for node in range(n):
            neighbors[node].sort(key=lambda x: scores[x], reverse=True)
            neighbors[node] = neighbors[node][:3]

        answer = -1

        # Try every edge as the middle edge
        for b, c in edges:
            for a in neighbors[b]:
                for d in neighbors[c]:
                    # All four nodes must be distinct
                    if a == c or d == b or a == d:
                        continue

                    total = scores[a] + scores[b] + scores[c] + scores[d]
                    answer = max(answer, total)

        return answer

The implementation begins by constructing an adjacency list for the graph. Each node stores its neighboring nodes.

Next, each neighbor list is sorted by neighbor score in descending order. We then truncate the list to only the top 3 neighbors. This ensures future processing remains constant time per edge.

The main loop treats every edge as the middle edge of a possible sequence. For each side of the edge, we iterate through the top neighbor candidates.

The distinctness checks ensure that no node appears more than once in the sequence.

Whenever a valid sequence is found, its score is computed and compared against the current best answer.

Finally, the maximum score is returned, or -1 if no valid sequence exists.

Go Solution

package main

import "sort"

func maximumScore(scores []int, edges [][]int) int {
	n := len(scores)

	neighbors := make([][]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]

		neighbors[u] = append(neighbors[u], v)
		neighbors[v] = append(neighbors[v], u)
	}

	// Keep only top 3 neighbors by score
	for i := 0; i < n; i++ {
		sort.Slice(neighbors[i], func(a, b int) bool {
			return scores[neighbors[i][a]] > scores[neighbors[i][b]]
		})

		if len(neighbors[i]) > 3 {
			neighbors[i] = neighbors[i][:3]
		}
	}

	answer := -1

	// Try every edge as the middle edge
	for _, edge := range edges {
		b, c := edge[0], edge[1]

		for _, a := range neighbors[b] {
			for _, d := range neighbors[c] {

				// All four nodes must be distinct
				if a == c || d == b || a == d {
					continue
				}

				total := scores[a] + scores[b] + scores[c] + scores[d]

				if total > answer {
					answer = total
				}
			}
		}
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version.

The main difference is the use of sort.Slice to sort neighbor lists. Slices are truncated to length 3 after sorting.

Go integers safely handle the maximum possible score because the sum never exceeds 4 * 10^8.

Worked Examples

Example 1

scores = [5,2,9,8,4]
edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

Step 1: Build Neighbor Lists

Node	Neighbors
0	[1,2]
1	[0,2,3]
2	[1,3,0,4]
3	[2,1]
4	[2]

Step 2: Sort by Neighbor Scores

Scores:

Node	Score
0	5
1	2
2	9
3	8
4	4

Sorted neighbor lists:

Node	Top Neighbors
0	[2,1]
1	[2,3,0]
2	[3,0,4]
3	[2,1]
4	[2]

Step 3: Evaluate Each Edge

Consider edge (1,2) as middle edge.

Possible left neighbors of 1:

[2,3,0]

Possible right neighbors of 2:

[3,0,4]

Check combinations:

a	b	c	d	Valid	Score
0	1	2	3	Yes	5+2+9+8 = 24
3	1	2	0	Yes	24
0	1	2	4	Yes	20
2	1	2	3	No	duplicate

Maximum becomes 24.

No other edge produces a better result.

Final answer:

Example 2

scores = [9,20,6,4,11,12]
edges = [[0,3],[5,3],[2,4],[1,3]]

Step 1: Build Neighbor Lists

Node	Neighbors
0	[3]
1	[3]
2	[4]
3	[0,5,1]
4	[2]
5	[3]

Step 2: Try Every Edge

For edge (0,3):

left side candidates from 0: [3]
right side candidates from 3: [1,5,0]

Every attempt contains duplicates because 0 has no alternative neighbor besides 3.

The same issue occurs for all edges.

No valid 4-node sequence exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E)	Each edge checks at most 3 × 3 neighbor combinations
Space	O(E)	Adjacency storage for graph edges

The neighbor truncation is the key optimization. Without it, high-degree nodes could cause expensive nested loops.

Because each node keeps at most 3 neighbors, every edge performs only a constant amount of work:

3 * 3 = 9 combinations

Thus, the total runtime scales linearly with the number of edges.

Test Cases

from typing import List

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)

        neighbors = [[] for _ in range(n)]

        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)

        for node in range(n):
            neighbors[node].sort(key=lambda x: scores[x], reverse=True)
            neighbors[node] = neighbors[node][:3]

        answer = -1

        for b, c in edges:
            for a in neighbors[b]:
                for d in neighbors[c]:
                    if a == c or d == b or a == d:
                        continue

                    answer = max(
                        answer,
                        scores[a] + scores[b] + scores[c] + scores[d]
                    )

        return answer

sol = Solution()

# Example 1
assert sol.maximumScore(
    [5,2,9,8,4],
    [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
) == 24  # standard valid sequence

# Example 2
assert sol.maximumScore(
    [9,20,6,4,11,12],
    [[0,3],[5,3],[2,4],[1,3]]
) == -1  # no valid sequence exists

# Simple chain of four nodes
assert sol.maximumScore(
    [1,2,3,4],
    [[0,1],[1,2],[2,3]]
) == 10  # only one valid path

# Dense graph
assert sol.maximumScore(
    [10,20,30,40,50],
    [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
) == 140  # choose top four nodes

# Graph with disconnected components
assert sol.maximumScore(
    [5,6,7,8,9],
    [[0,1],[1,2],[3,4]]
) == -1  # no path of length 3

# Duplicate avoidance test
assert sol.maximumScore(
    [100,1,1,100],
    [[0,1],[1,2],[2,3],[0,2]]
) == 202  # must avoid reusing nodes

# Minimum valid n
assert sol.maximumScore(
    [4,3,2,1],
    [[0,1],[1,2],[2,3]]
) == 10  # smallest graph with valid sequence

# Star graph
assert sol.maximumScore(
    [10,20,30,40,50],
    [[0,1],[0,2],[0,3],[0,4]]
) == -1  # impossible to form length-4 path

# High score hidden behind lower-degree nodes
assert sol.maximumScore(
    [1,100,90,80,70],
    [[0,1],[1,2],[2,3],[3,4]]
) == 340  # best chain uses all nodes

Test Summary

Test	Why
Example 1	Validates standard successful case
Example 2	Validates no-solution scenario
Simple chain	Tests basic path formation
Dense graph	Ensures maximum combination is found
Disconnected graph	Confirms invalid disconnected structures
Duplicate avoidance	Ensures node uniqueness logic works
Minimum valid n	Tests lower boundary constraint
Star graph	Verifies impossible topology handling
High score chain	Confirms optimal path discovery

Edge Cases

One important edge case occurs when the graph does not contain any path of length 3. A graph may contain many nodes and edges but still fail to produce a valid 4-node sequence. Star graphs are a classic example because every path must repeatedly pass through the center node, violating the distinctness requirement. The implementation handles this naturally because the answer remains -1 unless a valid combination is discovered.

Another important case involves overlapping high-score neighbors. Suppose the best neighbor candidate on both sides of the middle edge is the same node. A careless implementation might accidentally reuse that node twice. The explicit distinctness checks:

if a == c or d == b or a == d:

prevent this issue and guarantee all four nodes remain unique.

A third subtle edge case involves very high degree nodes. Some nodes may connect to thousands of neighbors. A naive nested iteration over all neighbors would become too slow. The optimization of storing only the top 3 neighbors keeps the runtime efficient while still preserving correctness. Even if some candidates conflict, three options are sufficient to ensure all valid high-scoring combinations are still explored.