Skip to main content
Talentd

Node With Highest Edge Score - Solution & Explanation

MediumHash TableGraph16 min readAsked at: Juspay
Practice this problem

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 by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].

The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.

Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.

 

Example 1:

Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- 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
Explanation:
- 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

Approach Overview

Problem Overview: You are given an array edges where index i has a directed edge to edges[i]. The edge score of a node is the sum of indices of nodes pointing to it. Your task is to compute the score for every node and return the node with the highest score (smallest index if there is a tie).

Approach 1: Brute Force Score Calculation (O(n²) time, O(1) space)

The straightforward idea is to compute the score of each node by scanning the entire edges array and summing all indices i where edges[i] == node. This means for every node j, you iterate through all n elements to check incoming edges. While the implementation is simple and uses constant extra space, it performs redundant scans and becomes inefficient for large inputs. This approach mainly helps you reason about how scores are defined before optimizing the solution.

Approach 2: Using an Array to Keep Score (O(n) time, O(n) space)

A more efficient approach accumulates scores in a dedicated array. Create a score array of size n, initialized to zero. Iterate once through the edges array. For each index i, add i to score[edges[i]]. This directly builds the total edge score for every node in a single pass. After filling the score array, scan it once more to find the node with the maximum score, resolving ties by selecting the smallest index. This method runs in linear time and works well because node IDs are already within the range [0, n-1]. Conceptually, the structure behaves like an adjacency accumulation in a graph.

Approach 3: Using a Hash Map for Flexibility (O(n) time, O(n) space)

If node identifiers were sparse or outside a predictable range, a hash map would be more flexible than a fixed array. Iterate through edges and update a map where the key is the destination node and the value stores the running score. Each iteration performs a constant-time hash lookup and addition. After building the map, iterate through the keys to determine the node with the maximum score. This approach uses the same accumulation idea as the array method but relies on a hash table for dynamic storage. It’s slightly heavier in memory and constant factors but easier to adapt when node IDs are not bounded.

Recommended for interviews: The array accumulation approach is the expected solution. It demonstrates that you recognize the fixed node range and can compute scores in one linear pass. Mentioning the brute force method first shows understanding of the scoring definition, while transitioning to the O(n) array solution shows optimization skills. The hash map version is useful to discuss when the problem generalizes beyond a fixed-size node set.

Approach 1: Using an array to keep score

This approach involves creating an array to store the scores of each node. We iterate through the given edges, and for each edge from node i to edges[i], we add i to the score of edges[i]. After populating the scores, we find the node with the highest score. In case of tie, we choose the smallest index.

This C solution initializes a score array of a sufficiently large size to accommodate all possible nodes. When iterating over the given edges array, we increment the score for the destination node by its source node index. Finally, we find the node with the highest score while handling ties by choosing the smallest index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), for storing the scores.

Try this approach in the editor →

Approach 2: Using a hash map for flexibility

This approach uses a hash map (or dictionary) to keep track of the scores of nodes. We traverse the edges and for each connection from node i to node edges[i], we update the score for edges[i] by adding i. After computing the scores for all nodes, we find the node with the highest score. If multiple nodes have the same score, choose the node with the smallest index.

This Python solution leverages a defaultdict for storing scores. As we iterate, the score of the destination node is increased by the source node index. After iterating through all nodes, we determine the node with the highest score, with ties resolved by index order.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), due to storing scores in the dictionary.

Try this approach in the editor →

Approach 3: Single Traversal

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

Next, we traverse the array edges. For each node i and its outgoing edge node j, we update cnt[j] to cnt[j] + i. If cnt[ans] < cnt[j] or cnt[ans] = cnt[j] and j < ans, we update ans to j.

Finally, return ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array edges.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using an array to keep score

Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), for storing the scores.

Using a hash map for flexibility

Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), due to storing scores in the dictionary.

Single Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Score CalculationO(n²)O(1)Useful for understanding the definition of edge score or when constraints are extremely small
Array Score AccumulationO(n)O(n)Best choice when node IDs are within 0..n-1 and you want the fastest solution
Hash Map AccumulationO(n)O(n)Preferred when node identifiers are sparse or not limited to a fixed range

Video Solution

Leetcode 2374 Node With Highest Edge Score | Graph Basics | Coding Decoded SDE Sheet • Coding Decoded • 847 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Node With Highest Edge Score easy or hard?
Node With Highest Edge Score is classified as a Medium problem. The core idea is simple accumulation, but recognizing that you can compute all scores in one linear pass instead of repeatedly scanning the array is the key insight.
Node With Highest Edge Score Python/Java solution
In Python or Java, iterate through the edges array and update a score array or hash map by adding the index to the destination node’s score. After accumulation, scan for the node with the maximum score while ensuring the smallest index is returned on ties.
How to solve Node With Highest Edge Score in O(n)?
Create a score array of size n initialized to zero. Loop through the edges array and add the index i to score[edges[i]]. Once all scores are accumulated, iterate through the score array to find the node with the highest value, breaking ties by choosing the smaller index.
What is the best approach for Node With Highest Edge Score?
The best approach uses an array to accumulate scores in one pass. Iterate through the edges array and add the index i to score[edges[i]]. After building the score array, scan it once to find the maximum score while keeping the smallest index on ties. This runs in O(n) time with O(n) space.
Is Node With Highest Edge Score asked at Google/Amazon/Meta?
This problem reflects common interview patterns around graph representation and hash-based aggregation. Variants of edge accumulation and counting using arrays or hash maps frequently appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Node With Highest Edge Score?
The primary data structure is an array used to accumulate edge scores for each node. A hash map can also be used to store scores dynamically if node identifiers are sparse or not limited to a fixed range.
What is the time complexity of Node With Highest Edge Score?
The optimal solution runs in O(n) time because each edge is processed exactly once and the score array is scanned once more to find the maximum. Space complexity is O(n) for storing the accumulated scores.

Ready to solve this problem?

Practice Node With Highest Edge Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sort Array by Increasing Frequency

Next

Sort Characters By Frequency