Node With Highest Edge Score - Practice Coding Problems

Node With Highest Edge Score - 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.

Input & Output

Example 1 — Basic Graph

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

› Output: 0

💡 Note: Node 0 has incoming edges from nodes 1 and 2, so score = 1 + 2 = 3. Node 1 has incoming edge from node 0, score = 0. Node 2 has incoming edge from node 3, score = 3. Node 0 has the highest score.

Example 2 — Tie Breaker

$ Input: edges = [1,2,3,0]

› Output: 0

💡 Note: Each node has exactly one incoming edge: scores are [3,0,1,2]. Node 0 has the highest score of 3.

Example 3 — Self Loop

$ Input: edges = [0,1,1]

› Output: 1

💡 Note: Node 0 points to itself (score = 0), nodes 1 and 2 point to node 1 (score = 1 + 2 = 3). Node 1 has the highest score.

Constraints

2 ≤ edges.length ≤ 10⁵
0 ≤ edges[i] < edges.length

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph where edges[i] points from i to edges[i]

Calculate Scores

Sum source node labels for each target

Find Winner

Return node with highest score

Key Takeaway

🎯 Key Insight: Each edge contributes its source node's value to the target's score

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is that each edge contributes the source node's label to the target node's score. The optimal approach uses a single pass to accumulate scores in O(n) time and O(n) space, much better than the O(n²) brute force solution.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each node, iterate through all edges to calculate its score
Single Pass with Array	O(n)	O(n)	Calculate all edge scores in one pass using an array to accumulate scores

Brute Force — Algorithm Steps

For each node i from 0 to n-1
Scan all edges to find which nodes point to i
Sum the labels of all pointing nodes
Track the node with maximum score

Visualization

Tap to expand

Step-by-Step Walkthrough

Target Node 0

Scan all edges to find sources pointing to 0

Target Node 1

Scan all edges to find sources pointing to 1

Find Maximum

Compare all scores and return highest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* edges, int n) {
    long long maxScore = -1;
    int result = 0;
    
    for (int target = 0; target < n; target++) {
        long long score = 0;
        for (int source = 0; source < n; source++) {
            if (edges[source] == target) {
                score += source;
            }
        }
        
        if (score > maxScore) {
            maxScore = score;
            result = target;
        }
    }
    
    return result;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int edges[10000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        edges[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(edges, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we scan all n edges to find incoming edges

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum score and result

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler