Node With Highest Edge Score

Med

#2161Time: O(n^2), where n is the number of nodes. For each of the n nodes, we iterate through the entire `edges` array of size n to find all incoming edges. This results in a nested loop structure, making it too slow for the problem's constraints.Space: O(1). We only use a few variables to keep track of the maximum score and the corresponding node, requiring constant extra space regardless of the input size.1 company

Data structures

Hash Table Graph

Companies

Juspay

Prompt

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 <= 10⁵
0 <= edges[i] < n
edges[i] != i

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code. It iterates through each node and, for each node, iterates through all edges again to find all incoming connections and calculate its score. This is straightforward but inefficient for the given constraints.

Algorithm

Initialize maxScore to -1 and resultNode to -1.
Iterate through each node j from 0 to n-1. This node j is the potential destination node whose score we want to calculate.
For each j, initialize currentScore = 0.
Start an inner loop, iterating through each node i from 0 to n-1. This node i is the potential source node.
Inside the inner loop, check if there is an edge from i to j (i.e., if edges[i] == j).
If an edge exists, add the label of the source node, i, to currentScore.
After the inner loop completes, currentScore holds the total edge score for node j.
Compare currentScore with maxScore. If currentScore is strictly greater, update maxScore = currentScore and resultNode = j.
After the outer loop finishes, resultNode will hold the answer. The tie-breaking rule (smallest index) is handled automatically because we iterate j from 0 to n-1 and only update for a strictly greater score.

Walkthrough

The brute-force method calculates the edge score for each node one by one. To find the score of a specific node j, we must scan the entire edges array to find all source nodes i that point to j.

We can use a nested loop structure. The outer loop iterates through every node j from 0 to n-1, treating it as the destination node. For each j, the inner loop iterates through every node i from 0 to n-1, treating it as a potential source node. If edges[i] is equal to j, it means there's an edge from i to j, so we add i to the score of j.

We maintain a variable maxScore to keep track of the highest score found so far and resultNode for the corresponding node's index. We update these whenever we find a node with a score greater than the current maxScore. The tie-breaking rule of returning the smallest index is naturally handled by iterating through the nodes in increasing order and only updating for strictly greater scores.

1class Solution {2    public int edgeScore(int[] edges) {3        int n = edges.length;4        long maxScore = -1;5        int resultNode = -1;6 7        for (int j = 0; j < n; j++) {8            long currentScore = 0;9            for (int i = 0; i < n; i++) {10                if (edges[i] == j) {11                    currentScore += i;12                }13            }14 15            if (currentScore > maxScore) {16                maxScore = currentScore;17                resultNode = j;18            }19        }20        return resultNode;21    }22}

Complexity

Time

O(n^2), where n is the number of nodes. For each of the n nodes, we iterate through the entire `edges` array of size n to find all incoming edges. This results in a nested loop structure, making it too slow for the problem's constraints.

Space

O(1). We only use a few variables to keep track of the maximum score and the corresponding node, requiring constant extra space regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Uses constant extra space, O(1), making it very memory-efficient.

Cons

Highly inefficient due to the O(n^2) time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error for inputs where n is large (e.g., n = 10^5).

A much more efficient approach is to calculate the scores for all nodes in a single pass. We can use an auxiliary array to store the scores. By iterating through the edges array just once, we can accumulate the scores for each destination node, avoiding the expensive nested loop.

Algorithm

Get the number of nodes, n, from the length of the edges array.
Create a long array named scores of size n and initialize all its elements to 0. This array will store the edge score for each node.
Iterate through the edges array with an index i from 0 to n-1.
For each i, the edge is from i to edges[i]. Add the score contribution i to the destination node: scores[edges[i]] += i.
After the loop, the scores array contains the final edge score for every node.
Initialize maxScore = -1 and resultNode = -1.
Iterate through the scores array from index i = 0 to n-1.
If scores[i] is greater than maxScore, update maxScore = scores[i] and resultNode = i.
Return resultNode.

Walkthrough

The inefficiency of the brute-force approach comes from repeatedly scanning the edges array. We can optimize this by changing our perspective. Instead of asking "what nodes point to me?" for each node, we can process each edge and say "I am contributing my label's value to my destination's score."

This leads to a two-pass linear time solution. In the first pass, we create an auxiliary array, scores, of size n to store the edge score for each node. A long array is necessary because the sum of labels can exceed the maximum value of a 32-bit integer. We iterate through the edges array from i = 0 to n-1. For each edge from i to edges[i], we add i to scores[edges[i]].

After this first pass, scores[j] will hold the total edge score for each node j. In the second pass, we simply iterate through the scores array to find the index that has the highest value. We maintain a maxScore and a resultNode and update them as we find higher scores. The tie-breaking rule is handled correctly by iterating from index 0 and only updating for strictly greater scores.

1class Solution {2    public int edgeScore(int[] edges) {3        int n = edges.length;4        // Use long for scores to prevent overflow, as the sum of indices can be large.5        long[] scores = new long[n];6 7        // First pass: calculate the score for each node.8        for (int i = 0; i < n; i++) {9            int destinationNode = edges[i];10            scores[destinationNode] += i;11        }12 13        // Second pass: find the node with the highest score.14        long maxScore = -1;15        int resultNode = -1;16 17        for (int i = 0; i < n; i++) {18            if (scores[i] > maxScore) {19                maxScore = scores[i];20                resultNode = i;21            }22        }23        24        return resultNode;25    }26}

Complexity

Time

O(n), where n is the number of nodes. We perform two separate, non-nested passes: one to populate the `scores` array and another to find the maximum score. The total time is O(n) + O(n) = O(n).

Space

O(n). We use an auxiliary array of size n to store the edge scores for each node. This is the dominant factor in space usage.

Trade-offs

Pros

Optimal time complexity of O(n), making it very fast and efficient.
Handles the given constraints with ease.
The logic is still straightforward and easy to follow.

Cons

Requires O(n) extra space for the scores array, which might be a concern for extremely memory-constrained environments, though it's acceptable for this problem.

Solutions

Solution

1class Solution {2public3  int edgeScore(int[] edges) {4    int n = edges.length;5    long[] cnt = new long[n];6    for (int i = 0; i < n; ++i) {7      cnt[edges[i]] += i;8    }9    int ans = 0;10    for (int i = 0; i < n; ++i) {11      if (cnt[ans] < cnt[i]) {12        ans = i;13      }14    }15    return ans;16  }17}

1class Solution {2public:3  int edgeScore(vector<int> &edges) {4    int n = edges.size();5    vector<long long> cnt(n);6    for (int i = 0; i < n; ++i) {7      cnt[edges[i]] += i;8    }9    int ans = 0;10    for (int i = 0; i < n; ++i) {11      if (cnt[ans] < cnt[i]) {12        ans = i;13      }14    }15    return ans;16  }17};

1class Solution:2    def edgeScore(self, edges: List[int]) -> int: cnt = Counter() for i, v in enumerate(edges): cnt[v] += i ans = 0 for i in range(len(edges)): if cnt[ans] < cnt[i]: ans = i return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem