LeetCode in Kotlin

2242. Maximum Score of a Node Sequence

Hard

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] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

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 * 10⁴
1 <= scores[i] <= 10⁸
0 <= edges.length <= 5 * 10⁴
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
There are no duplicate edges.

Solution

class Solution {
    fun maximumScore(scores: IntArray, edges: Array<IntArray>): Int {
        // store only top 3 nodes (having highest scores)
        val graph = Array(scores.size) { IntArray(3) }
        for (a in graph) {
            a.fill(-1)
        }
        for (edge in edges) {
            insert(edge[0], graph[edge[1]], scores)
            insert(edge[1], graph[edge[0]], scores)
        }
        var maxScore = -1
        for (edge in edges) {
            val u = edge[0]
            val v = edge[1]
            val score = scores[u] + scores[v]
            for (i in 0..2) {
                // if neighbour is current node, skip
                if (graph[u][i] == -1 || graph[u][i] == v) {
                    continue
                }
                for (j in 0..2) {
                    // if neighbour is current node or already choosen node, skip
                    if (graph[v][j] == -1 || graph[v][j] == u) {
                        continue
                    }
                    if (graph[v][j] == graph[u][i]) {
                        continue
                    }
                    maxScore = Math.max(maxScore, score + scores[graph[u][i]] + scores[graph[v][j]])
                }
            }
        }
        return maxScore
    }

    private fun insert(n: Int, arr: IntArray, scores: IntArray) {
        if (arr[0] == -1) {
            arr[0] = n
        } else if (arr[1] == -1) {
            if (scores[arr[0]] < scores[n]) {
                arr[1] = arr[0]
                arr[0] = n
            } else {
                arr[1] = n
            }
        } else if (arr[2] == -1) {
            if (scores[arr[0]] < scores[n]) {
                arr[2] = arr[1]
                arr[1] = arr[0]
                arr[0] = n
            } else if (scores[arr[1]] < scores[n]) {
                arr[2] = arr[1]
                arr[1] = n
            } else {
                arr[2] = n
            }
        } else {
            if (scores[arr[1]] < scores[n]) {
                arr[2] = arr[1]
                arr[1] = n
            } else if (scores[arr[2]] < scores[n]) {
                arr[2] = n
            }
        }
    }
}

This site is open source. Improve this page.