#2374

Medium

LeetCode Problem Workspace

Node With Highest Edge Score

Determine the node with the highest edge score in a graph using hash table aggregation and careful index tracking.

Problem Statement

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 as an integer array edges of length n, where edges[i] points from node i to edges[i].

The edge score of a node is the sum of all node labels that have an edge pointing to it. Return the node with the highest edge score. If multiple nodes have the same highest score, return the node with the smallest index.

Examples

Example 1

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

Output: 7

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.
The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11. Node 7 has the highest edge score so return 7.

Example 2

Input: edges = [2,0,0,2]

Output: 0

The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3. Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.

Constraints

n == edges.length
2 <= n <= 105
0 <= edges[i] < n
edges[i] != i

Solution Approach

Initialize Edge Scores

Create an array of length n to store edge scores. Iterate over edges and for each edge from node i to edges[i], increment the score of edges[i] by i. This hash table style accumulation captures all incoming contributions efficiently.

Track Maximum Node

While updating the edge scores, keep track of the maximum score and the corresponding node index. When a tie occurs, always favor the smaller node index to comply with the problem requirement.

Return Result

After processing all edges, the node stored as having the maximum score is the answer. This completes the solution with linear time and minimal extra space using a combined hash table and graph traversal pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each edge is processed once. Space complexity is O(n) for the edge score array acting as a hash table, allowing constant-time accumulation per edge.

What Interviewers Usually Probe

Expect candidates to recognize the pattern of aggregating contributions per node using a hash table.
Check if the candidate correctly handles ties by returning the smallest node index.
Look for linear time accumulation rather than nested loops that sum incoming edges repeatedly.

Common Pitfalls or Variants

Common pitfalls

Using nested loops to calculate edge scores, which leads to O(n^2) time and TLE.
Forgetting to break ties by choosing the smallest node index when multiple nodes share the max score.
Confusing node indices with edge targets, resulting in miscounted scores.

Follow-up variants

Compute the top k nodes with the highest edge scores instead of just one.
Modify the graph so nodes may have multiple outgoing edges and adjust aggregation accordingly.
Compute edge scores when nodes can have self-loops and validate the impact on the maximum node.

FAQ

What is the fastest way to calculate the node with the highest edge score?

Use an array to store each node's edge score, iterate through all edges once, and track the maximum score with its node index.

How should ties be handled in the node with highest edge score problem?

When multiple nodes have the same edge score, return the node with the smallest index to satisfy problem constraints.

Why is a hash table useful for this graph problem?

It allows constant-time accumulation of edge scores per node, avoiding repeated traversal of incoming edges and keeping the solution linear.

Can this approach handle very large graphs?

Yes, using an array as a hash table ensures O(n) time and O(n) space, making it feasible for graphs up to 10^5 nodes.

What pattern does 'Node With Highest Edge Score' follow?

It follows the 'Hash Table plus Graph' pattern, aggregating node contributions efficiently and tracking maxima during a single pass.

terminal

Solution

Solution 1: Single Traversal

We define an array $\textit{cnt}$ of length $n$, where $\textit{cnt}[i]$ represents the edge score of node $i$. Initially, all elements are $0$. We also define an answer variable $\textit{ans}$, initially set to $0$.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2368 reachable nodes with restrictions #2421 number of good paths #2508 add edges to make degrees of all nodes even