Skip to content

2242. Maximum Score of a Node Sequence 👍

  • Time: $O(|V| + |E|)$
  • Space: $O(|V| + |E|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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