Maximum Score of a Node Sequence LeetCode Solution

Problem – Maximum Score of a Node Sequence LeetCode Solution

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 4If 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.

Maximum Score of a Node Sequence LeetCode Solution in Java

    public int maximumScore(int[] A, int[][] edges) {
        int n = A.length;
        PriorityQueue<Integer>[] q = new PriorityQueue[n];
        for (int i = 0; i < n; i++)
            q[i] = new PriorityQueue<>((a, b) -> A[a] - A[b]);
        for (int[] e : edges) {
            q[e[0]].offer(e[1]);
            q[e[1]].offer(e[0]);
            if (q[e[0]].size() > 3) q[e[0]].poll();
            if (q[e[1]].size() > 3) q[e[1]].poll();
        }
        int res = -1;
        for (int[] edge : edges)
            for (int i : q[edge[0]])
                for (int j : q[edge[1]])
                    if (i != j && i != edge[1] && j != edge[0])
                        res = Math.max(res, A[i] + A[j] + A[edge[0]] + A[edge[1]]);  
        return res;
    }

Maximum Score of a Node Sequence LeetCode Solution in Python

    def maximumScore(self, A, edges):
        n = len(A)
        G = [[] for i in range(n)]
        for i,j in edges:
            G[i].append([A[j], j])
            G[j].append([A[i], i])
        for i in range(n):
            G[i] = nlargest(3, G[i])
            
        res = -1
        for i,j  in edges:
            for vii, ii in G[i]:
                for vjj, jj in G[j]:
                    if ii != jj and ii != j and j != ii:
                        res = max(res, vii + vjj + A[i] + A[j])
        return res

Maximum Score of a Node Sequence LeetCode Solution in C++

int maximumScore(vector<int>& sc, vector<vector<int>>& edges) {
    int res = -1;
    vector<vector<int>> al(sc.size());
    for (auto &e : edges) {
        al[e[0]].push_back(e[1]);
        al[e[1]].push_back(e[0]);
    }
    for(auto &l : al) {
        partial_sort(begin(l), begin(l) + min((int)l.size(), 3), end(l), [&](int i, int j){ return sc[i] > sc[j]; });
        l.resize(min((int)l.size(), 3));
    }
    for (auto &e : edges)
        for (int in : al[e[0]])
            for (int jn : al[e[1]])
                if (in != e[1] && jn != e[0] && in != jn)
                    res = max(res, sc[e[0]] + sc[e[1]] + sc[in] + sc[jn]);
    return res;
}

Maximum Score of a Node Sequence LeetCode Solution in Python3

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)
        edge = [[] for _ in range(n)]
        for u, v in edges:
            edge[u].append(v)
            edge[v].append(u)
        for l in edge:
            l.sort(key=lambda x:scores[x], reverse=True)
        ans = -1
        for u, v in edges:
            for x1 in range(min(3, len(edge[u]))):
                for y1 in range(min(3, len(edge[v]))):
                    x = edge[u][x1]
                    y = edge[v][y1]
                    if x != u and x != v and y != u and y != v and x != y:
                        ans = max(ans, scores[u] + scores[v] + scores[x] + scores[y])
        return ans
Maximum Score of a Node Sequence LeetCode Solution Review:

In our experience, we suggest you solve this Maximum Score of a Node Sequence LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum Score of a Node Sequence LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Maximum Score of a Node Sequence LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.