{x}
blog image

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.

Example 2:

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.

Solution Explanation

This problem asks to find the maximum score of a valid node sequence of length 4 in an undirected graph. A valid sequence means that adjacent nodes in the sequence are connected by an edge, and no node is repeated.

The solution uses a graph representation to efficiently find all valid sequences. The core idea is to pre-process the graph to store the top 3 highest-scoring neighbors for each node. This optimization reduces the search space significantly.

Algorithm:

  1. Graph Representation: The input edges is used to build an adjacency list representation of the graph. Each node stores a list of its neighbors.

  2. Preprocessing: For each node, the algorithm sorts its neighbors in descending order of their scores and keeps only the top 3 neighbors. This is because we only need to explore combinations of nodes involving the highest-scoring neighbors to maximize the chance of finding the maximum score.

  3. Iterate Through Edges: The algorithm iterates through each edge (a, b). For each edge, it considers all possible combinations of neighbors of a and b to form a sequence of length 4: [a, b, c, d]. c is a neighbor of a, and d is a neighbor of b.

  4. Validation and Score Calculation: Before calculating the score, it checks if the sequence is valid:

    • c must be different from a and b.
    • d must be different from a, b, and c.

  5. Maximum Score Tracking: If a valid sequence is found, its score (sum of node scores) is compared with the current maximum score (ans). The maximum score is updated accordingly.

  6. Return Value: Finally, the function returns the maximum score found. If no valid sequence of length 4 exists, it returns -1.

Time Complexity Analysis:

  • Building the adjacency list takes O(E) time, where E is the number of edges.
  • Sorting the neighbors for each node takes O(n * log k) time in the worst case, where k is the maximum degree of a node (typically, k <=3 because we are taking only top 3 neighbors). Since k is bounded by a constant, the time complexity becomes O(n).
  • Iterating through edges and checking combinations of neighbors takes O(nkk) which is O(n) since k is bounded by a constant(3).
  • Therefore, the overall time complexity is dominated by the preprocessing and iteration steps, resulting in O(E + n) time complexity.

Space Complexity Analysis:

  • The adjacency list uses O(V + E) space, where V is the number of vertices (nodes).
  • The space used for storing the top 3 neighbors for each node is O(n).
  • Therefore, the overall space complexity is O(V + E).

Code in Python3 and Java (provided in the original response) demonstrates this algorithm efficiently. The Java code utilizes ArrayList for dynamic resizing of the neighbor lists, which is appropriate for graphs where node degrees might vary. The python code utilizes the heapq.nlargest function to efficiently find the top 3 neighbors. Both are optimized to minimize unnecessary computations.