In this guide, you will get 2242. Maximum Score of a Node Sequence LeetCode Solution with the best time and space complexity. The solution to Maximum Score of a Node Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Score of a Node Sequence
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:
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.
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 * 104
1 <= scores[i] <= 108
0 <= edges.length <= 5 * 104
edges[i].length == 2
0 <= ai, bi <= n – 1
ai != bi
There are no duplicate edges.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)
2242. Maximum Score of a Node Sequence LeetCode Solution in C++
class Solution {
public:
int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
int ans = -1;
vector<set<pair<int, int>>> graph(scores.size()); // {(score, node)}
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].emplace(scores[v], v);
graph[v].emplace(scores[u], u);
if (graph[u].size() > 3)
graph[u].erase(graph[u].begin());
if (graph[v].size() > 3)
graph[v].erase(graph[v].begin());
}
// To find the target sequence: a - u - v - b, enumerate each edge (u, v),
// and find a (u's child) and b (v's child). That's why we find the 3
// children that have the highest scores because one of the 3 children is
// guaranteed to be valid.
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
for (const auto& [scoreA, a] : graph[u])
for (const auto& [scoreB, b] : graph[v])
if (a != b && a != v && b != u)
ans = max(ans, scoreA + scores[u] + scores[v] + scoreB);
}
return ans;
}
}; /* code provided by PROGIEZ */
2242. Maximum Score of a Node Sequence LeetCode Solution in Java
class Solution {
public int maximumScore(int[] scores, int[][] edges) {
final int n = scores.length;
int ans = -1;
Queue<Integer>[] graph = new Queue[n];
for (int i = 0; i < n; ++i)
graph[i] = new PriorityQueue<>((a, b) -> Integer.compare(scores[a], scores[b]));
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].offer(v);
graph[v].offer(u);
if (graph[u].size() > 3)
graph[u].poll();
if (graph[v].size() > 3)
graph[v].poll();
}
// To find the target sequence: a - u - v - b, enumerate each edge (u, v),
// and find a (u's child) and b (v's child). That's why we find the 3
// children that have the highest scores because one of the 3 children is
// guaranteed to be valid.
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
for (final int a : graph[u])
for (final int b : graph[v])
if (a != b && a != v && b != u)
ans = Math.max(ans, scores[a] + scores[u] + scores[v] + scores[b]);
}
return ans;
}
} // code provided by PROGIEZ
2242. Maximum Score of a Node Sequence LeetCode Solution in Python
class Solution:
def maximumScore(self, scores: list[int], edges: list[list[int]]) -> int:
n = len(scores)
ans = -1
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append((scores[v], v))
graph[v].append((scores[u], u))
for i in range(n):
graph[i] = heapq.nlargest(3, graph[i])
# To find the target sequence: a - u - v - b, enumerate each edge (u, v),
# and find a (u's child) and b (v's child). That's why we find the 3
# children that have the highest scores because one of the 3 children is
# guaranteed to be valid.
for u, v in edges:
for scoreA, a in graph[u]:
for scoreB, b in graph[v]:
if a != b and a != v and b != u:
ans = max(ans, scoreA + scores[u] + scores[v] + scoreB)
return ans # code by PROGIEZ
