Node With Highest Edge Score — Medium Problem & Solution

Problem statement

A directed graph has n nodes labelled 0 to n - 1, and every node has exactly one outgoing edge: node i points to node edges[i] (never to itself).

The edge score of a node v is the sum of the labels of all nodes that point to v.

Return the node with the highest edge score. If several nodes share the highest score, return the one with the smallest label.

Example 1

Input: edges = [1,4,1,4,2]
Output: 2
Explanation: Node 1 is pointed to by 0 and 2 (score 2), node 4 by 1 and 3 (score 4), node 2 by 4 (score 4). Nodes 2 and 4 tie; 2 is smaller.

Example 2

Input: edges = [2,0,0,2]
Output: 0
Explanation: Node 0 scores 1 + 2 = 3 and node 2 scores 0 + 3 = 3.

Constraints

• n == edges.length
• 2 <= n <= 10^5
• 0 <= edges[i] < n
• edges[i] != i

How to solve Node With Highest Edge Score

The edge score is a weighted in-degree: node i adds weight i to the node it points to. One accumulation pass and one arg-max pass solve it.

Approach

1. Create a 64-bit score array of length n, all zero.
2. For each i, add i to score[edges[i]].
3. Scan nodes from 0 to n - 1, keeping the node whose score is strictly greater than the best so far.
4. Return that node.

Why it works

Every edge i -> edges[i] is counted exactly once, in the score of its target, so the array holds the exact edge scores. Updating only on a strictly greater score while scanning in increasing label order returns the smallest label among the maxima.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• With n = 10^5 a node can score almost 5 * 10^9, which overflows a 32-bit integer.
• Use > rather than >= so ties keep the smaller label.
• Nodes nobody points to score 0 and can still be the answer only if every score is 0 (impossible here, but the scan handles it).

Reference solution

Python

from typing import List

def edgeScore(edges: List[int]) -> int:
    n = len(edges)
    score = [0] * n
    for i, t in enumerate(edges):
        score[t] += i
    best = 0
    for v in range(1, n):
        if score[v] > score[best]:
            best = v
    return best

JavaScript

var edgeScore = function(edges) {
    var n = edges.length;
    var score = new Array(n).fill(0);
    for (var i = 0; i < n; i++) score[edges[i]] += i;
    var best = 0;
    for (var v = 1; v < n; v++) if (score[v] > score[best]) best = v;
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Non-decreasing Subsequences Medium
• Minimum Operations to Write the Letter Y on a Grid Medium
• Difference of Number of Distinct Values on Diagonals Medium
• Find the Maximum Length of a Good Subsequence I Medium
• Extra Characters in a String Medium
• Maximum Earnings From Taxi Medium