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.

#2374

Medium

auto_awesome图

LeetCode 题解工作台

边积分最高的节点

给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都恰有一条出边。图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的有向边。节点 i 的边积分定义为：所有存在…

哈希表图

题目描述

给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。

图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的有向边。

节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的编号总和。

返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号最小的那个。

示例 1：

输入：edges = [1,0,0,0,0,7,7,5]
输出：7
解释：
- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。

示例 2：

输入：edges = [2,0,0,2]
输出：0
解释：
- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。
节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。

提示：

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

lightbulb

解题思路

方法一：一次遍历

我们定义一个长度为 $n$ 的数组 $\textit{cnt}$ ，其中 $\textit{cnt}[i]$ 表示节点 $i$ 的边积分，初始时所有元素均为 $0$ 。定义一个答案变量 $\textit{ans}$ ，初始时为 $0$ 。

接下来，我们遍历数组 $\textit{edges}$ ，对于每个节点 $i$ ，以及它的出边节点 $j$ ，我们更新 $\textit{cnt}[j]$ 为 $\textit{cnt}[j] + i$ 。如果 $\textit{cnt}[\textit{ans}] < \textit{cnt}[j]$ 或者 $\textit{cnt}[\textit{ans}] = \textit{cnt}[j]$ 且 $j < \textit{ans}$ ，我们更新 $\textit{ans}$ 为 $j$ 。

最后，返回 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{edges}$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2368 受限条件下可到达节点的数目 #2421 好路径的数目 #2508 添加边使所有节点度数都为偶数