Practice/Amazon/Leetcode 2374. Node With Highest Edge Score

Leetcode 2374. Node With Highest Edge Score

CodingOptional

Problem

You are given a directed graph represented by an array edges where each node has exactly one outgoing edge. The graph contains n nodes labeled from 0 to n-1, where n is the length of the edges array.

For node i, there is a directed edge pointing to node edges[i].

Each node has an influence score defined as the sum of all node labels that have edges pointing to it. In other words, if nodes a, b, and c all point to node x, then node x's influence score is a + b + c.

Your task is to find the node with the highest influence score. If multiple nodes share the highest score, return the node with the smallest label.

Requirements

1. Calculate the influence score for each node in the graph
2. Return the label of the node with the maximum influence score
3. Handle tie-breaking by returning the smallest node label when scores are equal
4. Process the graph efficiently given the constraint on input size

Constraints

• n == edges.length
• 1 <= n <= 100,000
• 0 <= edges[i] < n
• Each node has exactly one outgoing edge (functional graph property)

Examples

Example 1:

` Input: edges = [1, 2, 0, 2] Output: 2

Explanation: Node 0 points to node 1 Node 1 points to node 2 Node 2 points to node 0 Node 3 points to node 2

Influence scores:

• Node 0: receives from node 2 → score = 2
• Node 1: receives from node 0 → score = 0
• Node 2: receives from nodes 1 and 3 → score = 1 + 3 = 4
• Node 3: receives from no one → score = 0

Node 2 has the highest score of 4. `

Example 2:

` Input: edges = [2, 2, 1, 1] Output: 1

Explanation: Influence scores:

• Node 0: receives from no one → score = 0
• Node 1: receives from nodes 2 and 3 → score = 2 + 3 = 5
• Node 2: receives from nodes 0 and 1 → score = 0 + 1 = 1
• Node 3: receives from no one → score = 0

Node 1 has the highest score of 5. `

Example 3:

` Input: edges = [0] Output: 0

Explanation: Only one node exists, pointing to itself with score 0. `