Node With Highest Edge Score solution and explanation
9 more videos on this problem
Leetcode 2374 Node With Highest Edge Score | Graph Basics | Coding Decoded SDE SheetCoding Decoded · 6:00 · 847 views
2374. Node With Highest Edge Score | Leetcode Weekly Contest 306 | LeetCode 2374Bro Coders · 5:21 · 636 views
2374. Node With Highest Edge Score (Leetcode Medium)Programming Live with Larry · 5:27 · 164 views
Leetcode 2374. Node With Highest Edge Score | HindiThinkCode · 3:15 · 160 views
Node With Highest Edge Score |Leetcode weekly challenge | with and without graphCoding Techniques with Komal | Newton School · 10:34 · 144 views
Leetcode 2374. Node With Highest Edge Score - practice of graph theory concept - indegreeCode-Yao · 7:27 · 102 views
Leetcode 2374: Node With Highest Edge ScoreAlgorithms Casts · 9:47 · 65 views
2374 Node With Highest Edge Score | Leetcode Weekly contest 306Ashutosh sharma · 8:52 · 58 views
2374. Node With Highest Edge Score | LeetCode Weekly Contest 306 | Harshit Maurya | Arrays | GraphDSA Smashers · 8:33 · 55 views
leetcode 2374. Node With Highest Edge Score - weighted in-degreeCode-Yao · 6:21 · 48 views
The problem
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.length2 <= n <= 1050 <= edges[i] < nedges[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.
def nodeWithHighestEdgeScore(edges):
n = len(edges)
score = [0] * n
for i in range(n):
score[edges[i]] += i
max_score = 0
result_node = 0
for i in range(n):
if score[i] > max_score or (score[i] == max_score and i < result_node):
max_score = score[i]
result_node = i
return result_node
edges = [1,0,0,0,0,7,7,5]
print(nodeWithHighestEdgeScore(edges))import java.util.*;
public class Main {
public static int nodeWithHighestEdgeScore(int[] edges) {
int n = edges.length;
long[] score = new long[n];
for (int i = 0; i < n; i++) {
score[edges[i]] += i;
}
long maxScore = 0;
int resultNode = 0;
for (int i = 0; i < n; i++) {
if (score[i] > maxScore || (score[i] == maxScore && i < resultNode)) {
maxScore = score[i];
resultNode = i;
}
}
return resultNode;
}
public static void main(String[] args) {
int[] edges = {1,0,0,0,0,7,7,5};
System.out.println(nodeWithHighestEdgeScore(edges));
}
}#include <vector>
#include <iostream>
using namespace std;
int nodeWithHighestEdgeScore(vector<int>& edges) {
int n = edges.size();
vector<long long> score(n, 0);
for (int i = 0; i < n; i++) {
score[edges[i]] += i;
}
long long maxScore = 0;
int resultNode = 0;
for (int i = 0; i < n; i++) {
if (score[i] > maxScore || (score[i] == maxScore && i < resultNode)) {
maxScore = score[i];
resultNode = i;
}
}
return resultNode;
}
int main() {
vector<int> edges = {1,0,0,0,0,7,7,5};
cout << nodeWithHighestEdgeScore(edges) << endl;
return 0;
}function nodeWithHighestEdgeScore(edges) {
const n = edges.length;
const score = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
score[edges[i]] += i;
}
let maxScore = 0;
let resultNode = 0;
for (let i = 0; i < n; i++) {
if (score[i] > maxScore || (score[i] === maxScore && i < resultNode)) {
maxScore = score[i];
resultNode = i;
}
}
return resultNode;
}
const edges = [1,0,0,0,0,7,7,5];
console.log(nodeWithHighestEdgeScore(edges));#include <stdio.h>
#include <string.h>
#define MAX 100000
int nodeWithHighestEdgeScore(int* edges, int n) {
long long score[MAX] = {0};
for (int i = 0; i < n; i++) {
score[edges[i]] += i;
}
long long maxScore = 0;
int resultNode = 0;
for (int i = 0; i < n; i++) {
if (score[i] > maxScore || (score[i] == maxScore && i < resultNode)) {
maxScore = score[i];
resultNode = i;
}
}
return resultNode;
}
int main() {
int edges[] = {1,0,0,0,0,7,7,5};
int n = sizeof(edges) / sizeof(edges[0]);
printf("%d\n", nodeWithHighestEdgeScore(edges, n));
return 0;
}using System;
public class Solution {
public int NodeWithHighestEdgeScore(int[] edges) {
int n = edges.Length;
long[] score = new long[n];
for (int i = 0; i < n; i++) {
score[edges[i]] += i;
}
long maxScore = 0;
int resultNode = 0;
for (int i = 0; i < n; i++) {
if (score[i] > maxScore || (score[i] == maxScore && i < resultNode)) {
maxScore = score[i];
resultNode = i;
}
}
return resultNode;
}
public static void Main() {
int[] edges = {1,0,0,0,0,7,7,5};
Solution sol = new Solution();
Console.WriteLine(sol.NodeWithHighestEdgeScore(edges));
}
}In this Python solution, we use a list initialized to zero to store the scores of each node. We increment the score value of the destination node by its index in the edges list. The maximum score node is identified in another loop. If a tie occurs, the node with the smallest index is selected.
Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), due to the storage of scores in a list.
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.
def nodeWithHighestEdgeScoreUsingDict(edges):
from collections import defaultdict
score = defaultdict(int)
for i, v in enumerate(edges):
score[v] += i
max_score = 0
result_node = 0
for i in range(len(edges)):
if score[i] > max_score or (score[i] == max_score and i < result_node):
max_score = score[i]
result_node = i
return result_node
edges = [1,0,0,0,0,7,7,5]
print(nodeWithHighestEdgeScoreUsingDict(edges))import java.util.*;
public class MainMaps {
public static int nodeWithHighestEdgeScoreUsingMap(int[] edges) {
Map<Integer, Long> scoreMap = new HashMap<>();
for (int i = 0; i < edges.length; i++) {
scoreMap.put(edges[i], scoreMap.getOrDefault(edges[i], 0L) + i);
}
long maxScore = 0;
int resultNode = 0;
for (int i = 0; i < edges.length; i++) {
long currentScore = scoreMap.getOrDefault(i, 0L);
if (currentScore > maxScore || (currentScore == maxScore && i < resultNode)) {
maxScore = currentScore;
resultNode = i;
}
}
return resultNode;
}
public static void main(String[] args) {
int[] edges = {1,0,0,0,0,7,7,5};
System.out.println(nodeWithHighestEdgeScoreUsingMap(edges));
}
}function nodeWithHighestEdgeScoreUsingMap(edges) {
const score = new Map();
for (let i = 0; i < edges.length; i++) {
score.set(edges[i], (score.get(edges[i]) || 0) + i);
}
let maxScore = 0;
let resultNode = 0;
for (let i = 0; i < edges.length; i++) {
const currentScore = score.get(i) || 0;
if (currentScore > maxScore || (currentScore === maxScore && i < resultNode)) {
maxScore = currentScore;
resultNode = i;
}
}
return resultNode;
}
const edges = [1,0,0,0,0,7,7,5];
console.log(nodeWithHighestEdgeScoreUsingMap(edges));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.
Time complexity: O(n), where n is the number of nodes.
Space complexity: O(n), due to storing scores in the dictionary.
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.
function edgeScore(edges: number[]): number {
const n = edges.length;
const cnt: number[] = Array(n).fill(0);
let ans: number = 0;
for (let i = 0; i < n; ++i) {
const j = edges[i];
cnt[j] += i;
if (cnt[ans] < cnt[j] || (cnt[ans] === cnt[j] && j < ans)) {
ans = j;
}
}
return ans;
}func edgeScore(edges []int) (ans int) {
cnt := make([]int, len(edges))
for i, j := range edges {
cnt[j] += i
if cnt[ans] < cnt[j] || (cnt[ans] == cnt[j] && j < ans) {
ans = j
}
}
return
}impl Solution {
pub fn edge_score(edges: Vec<i32>) -> i32 {
let n = edges.len();
let mut cnt = vec![0_i64; n];
let mut ans = 0;
for (i, &j) in edges.iter().enumerate() {
let j = j as usize;
cnt[j] += i as i64;
if cnt[ans] < cnt[j] || (cnt[ans] == cnt[j] && j < ans) {
ans = j;
}
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using an array to keep score | Time complexity: O(n), where n is the number of nodes. |
| Using a hash map for flexibility | Time complexity: O(n), where n is the number of nodes. |
| Single Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Score Calculation | O(n²) | O(1) | Useful for understanding the definition of edge score or when constraints are extremely small |
| Array Score Accumulation | O(n) | O(n) | Best choice when node IDs are within 0..n-1 and you want the fastest solution |
| Hash Map Accumulation | O(n) | O(n) | Preferred when node identifiers are sparse or not limited to a fixed range |
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.