Node With Highest Edge Score — LeetCode 2374 Python Solution

The problem

You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge. The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].

Example

Input

edges = [1,0,0,0,0,7,7,5]

Output

7

Explanation

- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.

Python solution

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        ans = 0
        cnt = [0] * len(edges)
        for i, j in enumerate(edges):
            cnt[j] += i
            if cnt[ans] < cnt[j] or (cnt[ans] == cnt[j] and j < ans):
                ans = j
        return ans

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2374. Node With Highest Edge Score is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems