Node With the Heaviest Inflow

Medium

A directed graph has n nodes labeled 0 to n - 1. Every node has exactly one outgoing arrow: the arrow from node i leads to node points_to[i]. The weight of a node is the sum of the labels of all nodes whose arrows lead into it. A node with no incoming arrows has weight 0. Return the label of the node with the largest weight. If several nodes tie, return the smallest label.

Example 1

points_to=[3, 3, 0, 1] → 1

Nodes 0 and 1 point to 3, giving it weight 1. Node 2 points to 0 (weight 2), and node 3 points to 1 (weight 3). Node 1 wins.

Example 2

points_to=[1, 0, 1] → 1

Node 1 has weight 0 + 2 = 2 and node 0 has weight 1, so the answer is 1.

Example 3

points_to=[3, 0, 0, 1] → 0

Node 0 has weight 1 + 2 = 3, node 1 has weight 3 and node 3 has weight 0. Nodes 0 and 1 tie, so the smaller label wins: 0.

Constraints

n == len(points_to)
2 ≤ n ≤ 10⁵
0 ≤ points_to[i] < n
points_to[i] ≠ i

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Hash Table

Similar problems

Clear Tokens That Share a Line Medium Videos at a Friendship Distance Medium Dishes You Can Cook Medium Rooms Open from the Hall Medium Expand a Template With Variables Medium

Input

points_to=[3, 3, 0, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 14 tests on the server, hidden ones included.