Maximum Score of a Node Sequence

Hard

#2042Time: O(sum_{(u,v) in E} (deg(u) * deg(v))). In the worst case, where `deg` is the degree of a node, this can be `O(E * d_max^2)`, where `d_max` is the maximum degree. This can be too slow for the given constraints.Space: O(n + E) for storing the adjacency list, where `n` is the number of nodes and `E` is the number of edges.

Patterns

Enumeration

Algorithms

Sorting

Data structures

Array Graph

Prompt

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] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

A node sequence is valid if it meets the following conditions:

There is an edge connecting every pair of adjacent nodes in the sequence.
No node appears more than once in the sequence.

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.length
4 <= n <= 5 * 10⁴
1 <= scores[i] <= 10⁸
0 <= edges.length <= 5 * 10⁴
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
There are no duplicate edges.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach considers every edge in the graph as the central edge of a potential 4-node sequence. For each edge (u, v), it exhaustively searches through all neighbors of u and v to find the other two nodes that complete the sequence and maximize the score.

Algorithm

1. Construct an adjacency list adj for the graph.
1. Initialize maxScore = -1.
1. For each edge (u, v) in the input edges array:
1. For each neighbor a of u:
1. If `a` is the same as `v`, continue to the next neighbor.
1. For each neighbor `d` of `v`:
1. If `d` is the same as `u` or `a`, continue to the next neighbor.
1. Calculate `currentScore = scores[a] + scores[u] + scores[v] + scores[d]`.
1. Update `maxScore = max(maxScore, currentScore)`.
1. Return maxScore.

Walkthrough

First, we build an adjacency list representation of the graph from the given edges. We initialize a variable maxScore to -1. We then iterate through every edge (u, v) in the input edges array. These two nodes will form the middle part of our 4-node sequence a-u-v-d. For each edge (u, v), we need to find two other nodes: a, a neighbor of u, and d, a neighbor of v. The four nodes a, u, v, d must all be distinct. To do this, we use nested loops. The outer loop iterates through all neighbors of u (let's call a neighbor a). The inner loop iterates through all neighbors of v (let's call a neighbor d). Inside the inner loop, we check if the four nodes form a valid sequence of distinct nodes: a != v, d != u, and a != d. If they are distinct, we calculate the total score: scores[a] + scores[u] + scores[v] + scores[d]. We update maxScore with this score if it's higher than the current maxScore. After checking all edges and all their neighbor combinations, maxScore will hold the result. If no such sequence of length 4 is found, maxScore remains -1.

1import java.util.*;2 3class Solution {4    public int maximumScore(int[] scores, int[][] edges) {5        int n = scores.length;6        List<Integer>[] adj = new ArrayList[n];7        for (int i = 0; i < n; i++) {8            adj[i] = new ArrayList<>();9        }10        for (int[] edge : edges) {11            adj[edge[0]].add(edge[1]);12            adj[edge[1]].add(edge[0]);13        }14 15        long maxScore = -1;16 17        for (int[] edge : edges) {18            int u = edge[0];19            int v = edge[1];20 21            for (int neighborU : adj[u]) {22                if (neighborU == v) continue;23                for (int neighborV : adj[v]) {24                    if (neighborV == u || neighborV == neighborU) continue;25                    26                    long currentScore = (long) scores[u] + scores[v] + scores[neighborU] + scores[neighborV];27                    maxScore = Math.max(maxScore, currentScore);28                }29            }30        }31 32        return (int) maxScore;33    }34}

Complexity

Time

O(sum_{(u,v) in E} (deg(u) * deg(v))). In the worst case, where `deg` is the degree of a node, this can be `O(E * d_max^2)`, where `d_max` is the maximum degree. This can be too slow for the given constraints.

Space

O(n + E) for storing the adjacency list, where `n` is the number of nodes and `E` is the number of edges.

Trade-offs

Pros

Conceptually simpler than the optimized approach.
Correctly finds the maximum score.

Cons

Inefficient time complexity, likely to time out on large test cases, especially for graphs with nodes of high degree.

This approach significantly optimizes the search for the two outer nodes of the sequence. It's based on the key insight that for any central edge (u, v), the optimal outer nodes a (neighbor of u) and d (neighbor of v) must be among the highest-scoring neighbors of u and v. Specifically, we only need to consider the top 3 neighbors with the highest scores for each node.

Algorithm

1. Create an adjacency list adj where adj[i] stores pairs of (score, neighbor_id) for each neighbor of node i.
1. For each node i from 0 to n-1:
1. Sort adj[i] in descending order based on scores.
1. Trim adj[i] to keep only the top 3 neighbors.
1. Initialize maxScore = -1.
1. For each edge (u, v) in edges:
1. For each top neighbor a of u in its trimmed list:
1. For each top neighbor `d` of `v` in its trimmed list:
1. If `a`, `u`, `v`, `d` are all distinct (i.e., `a != v`, `d != u`, `a != d`):
1. Calculate `currentScore = scores[u] + scores[v] + scores[a] + scores[d]`.
1. Update `maxScore = max(maxScore, currentScore)`.
1. Return maxScore.

Walkthrough

The core idea is to iterate through each edge (u, v) as the middle part of the sequence a-u-v-d. To maximize the total score, we need to pick neighbors a and d with the highest possible scores. A crucial observation is that for any optimal sequence a*-u-v-d*, the node a* must be one of the top-scoring neighbors of u. If a* wasn't, say, in the top 3, there would be at least three other neighbors of u with scores greater than or equal to scores[a*]. At most two of these could be v or d*, leaving at least one high-scoring neighbor that could replace a* to yield an equal or better score. The same logic applies to d* and v. Therefore, we only need to check combinations from the top 3 neighbors of u and v.

The algorithm proceeds as follows:

First, we build an adjacency list where for each node, we store its neighbors paired with their scores.
For each node, we sort its neighbors in descending order based on their scores.
We then trim each neighbor list to keep only the top 3. This pre-computation step is key to the efficiency.
We initialize maxScore to -1.
We iterate through each edge (u, v) in the graph.
For each edge, we perform a small, constant-time search. We iterate through the (at most 3) pre-computed top neighbors of u (let's call one a) and the (at most 3) top neighbors of v (let's call one d). This results in at most 3 * 3 = 9 checks per edge.
In each check, we ensure the four nodes a, u, v, d are distinct.
If they are, we calculate the sum of their scores and update maxScore.
Finally, we return maxScore.

1import java.util.*;2 3class Solution {4    public int maximumScore(int[] scores, int[][] edges) {5        int n = scores.length;6        // Store neighbors as pairs of (score, node_id)7        List<int[]>[] adj = new ArrayList[n];8        for (int i = 0; i < n; i++) {9            adj[i] = new ArrayList<>();10        }11        for (int[] edge : edges) {12            int u = edge[0];13            int v = edge[1];14            adj[u].add(new int[]{scores[v], v});15            adj[v].add(new int[]{scores[u], u});16        }17 18        // Sort neighbors by score in descending order and keep top 319        for (int i = 0; i < n; i++) {20            Collections.sort(adj[i], (a, b) -> b[0] - a[0]);21            if (adj[i].size() > 3) {22                adj[i] = adj[i].subList(0, 3);23            }24        }25 26        long maxScore = -1;27 28        // Iterate through each middle edge (u, v)29        for (int[] edge : edges) {30            int u = edge[0];31            int v = edge[1];32            33            // Iterate through top neighbors of u and v34            for (int[] neighborU : adj[u]) {35                int a = neighborU[1];36                for (int[] neighborV : adj[v]) {37                    int d = neighborV[1];38                    39                    // Check for distinct nodes40                    if (a != v && d != u && a != d) {41                        long currentScore = (long) scores[u] + scores[v] + scores[a] + scores[d];42                        maxScore = Math.max(maxScore, currentScore);43                    }44                }45            }46        }47 48        return (int) maxScore;49    }50}

Complexity

Time

O(E * log(d_max) + E). The dominant part is sorting the adjacency lists for all nodes, which is bounded by `O(E * log n)`. The main loop runs in `O(E)` time since the inner loops are constant time (at most 3*3=9). So, the total time is `O(E * log n)`.

Space

O(n + E) to build the initial adjacency list. The trimmed list takes O(n) space. So, the total space is O(n + E).

Trade-offs

Pros

Highly efficient, with a time complexity that handles the given constraints easily.
The pre-computation step of sorting and trimming neighbors drastically reduces the search space.

Cons

Slightly more complex to implement due to the pre-processing step.
Requires careful reasoning to prove that considering only the top 3 neighbors is sufficient.

Solutions

Solution

1class Solution {2public3  int maximumScore(int[] scores, int[][] edges) {4    int n = scores.length;5    List<Integer>[] g = new List[n];6    Arrays.setAll(g, k->new ArrayList<>());7    for (int[] e : edges) {8      int a = e[0], b = e[1];9      g[a].add(b);10      g[b].add(a);11    }12    for (int i = 0; i < n; ++i) {13      g[i].sort((a, b)->scores[b] - scores[a]);14      g[i] = g[i].subList(0, Math.min(3, g[i].size()));15    }16    int ans = -1;17    for (int[] e : edges) {18      int a = e[0], b = e[1];19      for (int c : g[a]) {20        for (int d : g[b]) {21          if (c != b && c != d && a != d) {22            int t = scores[a] + scores[b] + scores[c] + scores[d];23            ans = Math.max(ans, t);24          }25        }26      }27    }28    return ans;29  }30}

1class Solution:2    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int: g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) for k in g . keys(): g[k] = nlargest(3, g[k], key=lambda x: scores[x]) ans = - 1 for a, b in edges: for c in g[a]: for d in g[b]: if b != c != d != a: t = scores[a] + scores[b] + scores[c] + scores[d] ans = max(ans, t) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem