Watch 6 video solutions for Maximum Score of a Node Sequence, a hard level problem involving Array, Graph, Sorting. This walkthrough by Hua Hua has 5,538 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an undirected graph with n nodes, numbered from 0 to n - 1.
You are given a 0-indexed integer array scores of length n where scores[i] denotes the score of node i. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A node sequence is valid if it meets the following conditions:
The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.
Return the maximum score of a valid node sequence with a length of 4. If no such sequence exists, return -1.
Example 1:
Input: scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] Output: 24 Explanation: The figure above shows the graph and the chosen node sequence [0,1,2,3]. The score of the node sequence is 5 + 2 + 9 + 8 = 24. It can be shown that no other node sequence has a score of more than 24. Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24. The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
Example 2:
Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]] Output: -1 Explanation: The figure above shows the graph. There are no valid node sequences of length 4, so we return -1.
Constraints:
n == scores.length4 <= n <= 5 * 1041 <= scores[i] <= 1080 <= edges.length <= 5 * 104edges[i].length == 20 <= ai, bi <= n - 1ai != biProblem Overview: You are given a graph where each node has a score. The task is to choose four distinct nodes a → b → c → d such that edges exist between consecutive nodes and the total score score[a] + score[b] + score[c] + score[d] is maximized.
Approach 1: Graph Traversal with Backtracking (O(E * d²) time, O(V + E) space)
Build an adjacency list for the graph. For every edge (b, c), treat it as the middle of the sequence. Enumerate neighbors of b as candidates for a and neighbors of c as candidates for d. Skip nodes that repeat since all four nodes must be distinct. This effectively performs controlled enumeration of possible sequences around each edge. The complexity depends on node degrees, since every pair of neighbors around the middle edge is tested. This works well for small or moderately dense graphs but can degrade when nodes have large adjacency lists.
Approach 2: Priority Queue for Top Nodes (O(E log V) time, O(V + E) space)
The key insight: when extending the middle edge (b, c), you only care about the highest scoring neighbors of b and c. Maintain the top three neighbors for every node based on score using a sorting step or a small priority queue. For each edge, combine the top candidates from both sides and check valid combinations where all nodes differ. Because each node stores only a few best neighbors, the number of checks per edge stays constant. This drastically reduces enumeration while still guaranteeing the optimal score.
Recommended for interviews: The priority queue / top‑neighbors approach is what interviewers expect. Starting with the brute enumeration around each edge shows you understand the structure of the sequence, but optimizing by keeping only the top few neighbors demonstrates strong graph reasoning and pruning of the search space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Traversal with Backtracking | O(E * d²) | O(V + E) | When implementing a straightforward enumeration around each edge or when node degrees are small |
| Priority Queue for Top Nodes | O(E log V) | O(V + E) | General case and interview settings where pruning neighbors to top candidates avoids quadratic checks |