Problem Description
Given an undirected graph with n nodes and a 0-indexed integer array scores, return the maximum score of a valid node sequence of length 4. A valid sequence must have edges connecting every pair of adjacent nodes and no node can appear more than once. If no such sequence exists, return -1.
Key Insights
- A valid node sequence consists of 4 distinct nodes connected by edges in the graph.
- The graph can be represented using an adjacency list for efficient traversal.
- We need to consider combinations of nodes and check if they form valid sequences based on the edges.
- The maximum score of a valid sequence is the sum of the scores of its nodes.
Space and Time Complexity
Time Complexity: O(E + V^3) where E is the number of edges and V is the number of nodes (due to combinations of nodes). Space Complexity: O(V + E) for storing the adjacency list.
Solution
To solve this problem, we can use a combination of depth-first search (DFS) or breadth-first search (BFS) to explore all possible sequences of length 4. We will keep track of the maximum score found during the exploration. The adjacency list will help us efficiently check if two nodes are directly connected. We will iterate through all nodes and for each node, explore its neighbors recursively to form valid sequences.