Maximum Score of a Node Sequence
01 · Problem
You are given an undirected graph with n nodes labelled 0 to n - 1. Each node i has a score scores[i], and edges[j] = [a, b] connects nodes a and b.
A sequence of nodes is valid when it has exactly 4 nodes, all of them distinct, and every pair of consecutive nodes in the sequence is connected by an edge. In other words, it is a simple path with 3 edges.
The score of a sequence is the sum of the scores of its nodes. Return the maximum score of any valid sequence, or -1 if no valid sequence exists.
02 · Examples
scores = [4,7,1,6,3], edges = [[0,1],[1,2],[2,3],[3,4],[1,3]]
20
The sequence 0 -> 1 -> 3 -> 4 is valid and scores 4 + 7 + 6 + 3 = 20. No other 4-node path scores higher.
scores = [3,5,2,8], edges = [[0,1],[0,2],[0,3]]
-1
The graph is a star centred at node 0. Any path can visit at most 3 nodes, so no valid 4-node sequence exists.
scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
24
The sequence 0 -> 2 -> 3 -> 1 is valid and scores 5 + 9 + 8 + 2 = 24. Node 4 only touches node 2, so any path using it ends there and scores at most 4 + 9 + 8 + 2 = 23.
03 · Constraints
- 014 <= n == scores.length <= 5 * 104
- 021 <= scores[i] <= 108
- 030 <= edges.length <= 5 * 104
- 04edges[j].length == 2, 0 <= a, b <= n - 1, a != b
- 05There are no duplicate edges
04 · Optimal complexity
- Time
- O(n + e)
- Space
- O(n + e)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.