Maximum Score of a Node Sequence — Problem & Solution
Maximum Score of a Node Sequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Score of a Node Sequence is a hard coding problem on arrays, sorting and graph, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Graph, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected graph has n nodes numbered 0 to n - 1. Node i carries the score scores[i], and each edges[j] = [a, b] is an undirected edge between a and b.
A node sequence is valid when every pair of adjacent nodes in it is joined by an edge and no node appears twice. Its score is the sum of its nodes' scores.
Return the maximum score of a valid sequence of length exactly 4, or -1 if there is none.
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 sequence [0,1,2,3] scores 5 + 2 + 9 + 8 = 24; no length-4 sequence scores more.
Example 2
Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
Output: -1
Explanation: Every edge touches node 3 or is the lone edge 2–4, so no path visits four distinct nodes.
Example 3
Input: scores = [1,1,1,1], edges = [[0,1],[1,2],[2,3]]
Output: 4
Constraints
n == scores.length4 <= n <= 5 * 10^41 <= scores[i] <= 10^80 <= edges.length <= 5 * 10^4edges[j].length == 20 <= a, b <= n - 1a != bthere are no duplicate edges
Hints for Maximum Score of a Node Sequence
Hint 1
A sequence of four nodes is
a – b – c – d: one middle edge(b, c)with one extra neighbour on each side.Hint 2
Fix the middle edge. The best
ais a high-scoring neighbour ofb, and the bestda high-scoring neighbour ofc— but they must avoidc,band each other.Hint 3
Those three exclusions can rule out at most two candidates on a side, so keeping only the three highest-scoring neighbours of every node is enough.
How to solve Maximum Score of a Node Sequence
Enumerate the middle edge (b, c) of the sequence. The end nodes are then a neighbour of b and a neighbour of c, chosen as large as possible subject to being distinct from the other three nodes. At most three nodes can be forbidden for each end, so only each node's top three neighbours by score ever matter.
Approach
- For every node keep its three highest-scoring neighbours.
- For each edge
(b, c): for eachaintop(b)and eachdintop(c), skip ifa == c,d == bora == d; otherwise evaluatescores[a] + scores[b] + scores[c] + scores[d]. - Return the best value, or
-1if no combination was valid.
Why it works
Suppose the optimal sequence uses an end a that is not among b's top three neighbours. Of those three, at most two are excluded (c and d), so one remaining top neighbour scores at least as much as a and gives a valid sequence too. The same argument applies to d, so restricting both ends to the top three loses nothing.
Complexity
- Time —
O(n + m) - Space —
O(n + m)
Pitfalls
- Try both orientations of every edge — each end of the middle edge can play
b. - Top-two is not enough:
canddcan both be amongb's best neighbours. - The sum of four scores reaches
4 · 10^8, still within a 32-bit integer.
Reference solution
Python
from typing import List
def maximumScore(scores: List[int], edges: List[List[int]]) -> int:
n = len(scores)
top = [[] for _ in range(n)]
def add(u, v):
t = top[u]
t.append(v)
t.sort(key=lambda x: -scores[x])
if len(t) > 3:
t.pop()
for a, b in edges:
add(a, b)
add(b, a)
best = -1
for a, b in edges:
for x, y in ((a, b), (b, a)):
base = scores[x] + scores[y]
for p in top[x]:
if p == y:
continue
for q in top[y]:
if q == x or q == p:
continue
best = max(best, base + scores[p] + scores[q])
return bestJava
public static int maximumScore(int[] scores, int[][] edges) {
int n = scores.length;
int[][] top = new int[n][3];
for (int[] t : top) Arrays.fill(t, -1);
for (int[] e : edges) {
for (int side = 0; side < 2; side++) {
int u = e[side], v = e[1 - side];
for (int i = 0; i < 3; i++) {
if (top[u][i] == -1 || scores[v] > scores[top[u][i]]) {
for (int j = 2; j > i; j--) top[u][j] = top[u][j - 1];
top[u][i] = v;
break;
}
}
}
}
int best = -1;
for (int[] e : edges) {
for (int side = 0; side < 2; side++) {
int x = e[side], y = e[1 - side];
for (int p : top[x]) {
if (p == -1 || p == y) continue;
for (int q : top[y]) {
if (q == -1 || q == x || q == p) continue;
best = Math.max(best, scores[p] + scores[x] + scores[y] + scores[q]);
}
}
}
}
return best;
}C++
int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
int n = scores.size();
vector<array<int, 3>> top(n, {-1, -1, -1});
for (auto& e : edges) {
for (int side = 0; side < 2; side++) {
int u = e[side], v = e[1 - side];
for (int i = 0; i < 3; i++) {
if (top[u][i] == -1 || scores[v] > scores[top[u][i]]) {
for (int j = 2; j > i; j--) top[u][j] = top[u][j - 1];
top[u][i] = v;
break;
}
}
}
}
int best = -1;
for (auto& e : edges) {
for (int side = 0; side < 2; side++) {
int x = e[side], y = e[1 - side];
for (int p : top[x]) {
if (p == -1 || p == y) continue;
for (int q : top[y]) {
if (q == -1 || q == x || q == p) continue;
best = max(best, scores[p] + scores[x] + scores[y] + scores[q]);
}
}
}
}
return best;
}JavaScript
var maximumScore = function(scores, edges) {
var n = scores.length;
var top = new Array(3 * n);
for (var i = 0; i < 3 * n; i++) top[i] = -1;
var add = function(u, v) {
for (var i = 0; i < 3; i++) {
var cur = top[3 * u + i];
if (cur === -1 || scores[v] > scores[cur]) {
for (var j = 2; j > i; j--) top[3 * u + j] = top[3 * u + j - 1];
top[3 * u + i] = v;
return;
}
}
};
for (var e = 0; e < edges.length; e++) { add(edges[e][0], edges[e][1]); add(edges[e][1], edges[e][0]); }
var best = -1;
for (var e2 = 0; e2 < edges.length; e2++) {
for (var side = 0; side < 2; side++) {
var x = edges[e2][side], y = edges[e2][1 - side];
for (var i2 = 0; i2 < 3; i2++) {
var p = top[3 * x + i2];
if (p === -1 || p === y) continue;
for (var j2 = 0; j2 < 3; j2++) {
var q = top[3 * y + j2];
if (q === -1 || q === x || q === p) continue;
var s = scores[p] + scores[x] + scores[y] + scores[q];
if (s > best) best = s;
}
}
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms