Maximum Score of a Node Sequence

Hard
1702.

Maximum Score of a Node Sequence

Maximum Score of a Node Sequence is a hard coding problem on arrays, sorting and graph, asked in Amazon and Google interviews.

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.length
  • 4 <= n <= 5 * 10^4
  • 1 <= scores[i] <= 10^8
  • 0 <= edges.length <= 5 * 10^4
  • edges[j].length == 2
  • 0 <= a, b <= n - 1
  • a != b
  • there are no duplicate edges
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} scores
 * @param {number[][]} edges
 * @return {number}
 */
var maximumScore = function(scores, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 4 <= n <= 5 * 10^4
  • 1 <= scores[i] <= 10^8
  • 0 <= edges.length <= 5 * 10^4
  • edges[j].length == 2
  • 0 <= a, b <= n - 1
  • a != b
  • there are no duplicate edges

Hints for Maximum Score of a Node Sequence

  1. Hint 1

    A sequence of four nodes is a – b – c – d: one middle edge (b, c) with one extra neighbour on each side.

  2. Hint 2

    Fix the middle edge. The best a is a high-scoring neighbour of b, and the best d a high-scoring neighbour of c — but they must avoid c, b and each other.

  3. 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

  1. For every node keep its three highest-scoring neighbours.
  2. For each edge (b, c): for each a in top(b) and each d in top(c), skip if a == c, d == b or a == d; otherwise evaluate scores[a] + scores[b] + scores[c] + scores[d].
  3. Return the best value, or -1 if 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: c and d can both be among b'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 best

Java

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