LeetCode 2374 - Node With Highest Edge Score

The problem asks us to analyze a directed graph where each node has exactly one outgoing edge, represented by the array edges. Each index i represents a node, and edges[i] represents a directed edge from node i to node edges[i].

leetcodemediumhash-tablegraph-theory

LeetCode Problem 2374

Difficulty: 🟡 Medium
Topics: Hash Table, Graph Theory

Solution

Problem Understanding

The problem asks us to analyze a directed graph where each node has exactly one outgoing edge, represented by the array edges. Each index i represents a node, and edges[i] represents a directed edge from node i to node edges[i]. We are required to calculate the edge score for each node, defined as the sum of the labels of all nodes pointing to it. The goal is to find the node with the highest edge score, returning the one with the smallest index in case of ties.

In simpler terms, we are counting the sum of incoming node labels for each node and identifying the maximum. The constraints specify up to 100,000 nodes (n <= 10^5), which implies that an efficient linear approach is necessary. Edge cases include multiple nodes with the same maximum edge score, nodes with no incoming edges, or graphs where all nodes point in a chain or cycle.

Approaches

The brute-force approach would iterate through each node and, for every node, iterate through the edges array to sum labels of nodes pointing to it. This guarantees correctness, but the complexity would be O(n^2), which is too slow for n = 10^5.

The optimal approach leverages the fact that each node points to exactly one other node. We can iterate through the array once, and for each node i, add its label to the edge score of edges[i]. This results in a linear-time solution with O(n) space to store edge scores.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Iterate for each node through all edges to sum incoming labels
Optimal O(n) O(n) Single pass to accumulate edge scores, then find max

Algorithm Walkthrough

  1. Initialize an array score of length n to store the cumulative edge score for each node. All elements start at 0.
  2. Iterate through each node i from 0 to n-1.
  3. For each node i, increment score[edges[i]] by i. This accumulates all nodes pointing to each node.
  4. Initialize two variables: max_score to track the current highest edge score, and result_node to track the node index corresponding to max_score.
  5. Iterate through the score array. For each node i, if score[i] exceeds max_score, update max_score and result_node with i. If score[i] equals max_score and i is smaller than result_node, update result_node to i.
  6. Return result_node.

Why it works: By iterating through all nodes exactly once and accumulating their labels into the target nodes’ scores, we ensure that all incoming edges are counted. Tracking the maximum score and the smallest index simultaneously ensures the correct tie-breaking behavior.

Python Solution

from typing import List

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)
        score = [0] * n

        for i, target in enumerate(edges):
            score[target] += i

        max_score = -1
        result_node = -1

        for i, s in enumerate(score):
            if s > max_score or (s == max_score and i < result_node):
                max_score = s
                result_node = i

        return result_node

Explanation: We first allocate a score array to store the edge scores. Iterating over edges, we add each node’s label to the node it points to. After accumulation, we scan score to determine the maximum, breaking ties using the smallest node index.

Go Solution

func edgeScore(edges []int) int {
    n := len(edges)
    score := make([]int, n)

    for i, target := range edges {
        score[target] += i
    }

    maxScore := -1
    resultNode := -1

    for i, s := range score {
        if s > maxScore || (s == maxScore && i < resultNode) {
            maxScore = s
            resultNode = i
        }
    }

    return resultNode
}

Go-specific notes: We use a slice score to store the edge scores. Integer overflow is not a concern with the given constraints. Slice indexing is 0-based, matching the problem requirements. Tie-breaking logic uses a standard comparison to ensure the smallest index is returned.

Worked Examples

Example 1: edges = [1,0,0,0,0,7,7,5]

i edges[i] Action score array after step
0 1 score[1] += 0 [0,0,0,0,0,0,0,0] → [0,0,0,0,0,0,0,0]
1 0 score[0] += 1 [1,0,0,0,0,0,0,0]
2 0 score[0] += 2 [3,0,0,0,0,0,0,0]
3 0 score[0] += 3 [6,0,0,0,0,0,0,0]
4 0 score[0] += 4 [10,0,0,0,0,0,0,0]
5 7 score[7] += 5 [10,0,0,0,0,0,0,5]
6 7 score[7] += 6 [10,0,0,0,0,0,0,11]
7 5 score[5] += 7 [10,0,0,0,0,7,0,11]

Max score is 11 at node 7 → return 7.

Example 2: edges = [2,0,0,2]

i edges[i] score array
0 2 [0,0,0,0] → [0,0,0,0]
1 0 [1,0,0,0]
2 0 [3,0,0,0]
3 2 [3,0,3,0]

Max score is 3 for nodes 0 and 2 → return smallest index 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to accumulate scores and another pass to find max
Space O(n) Array of length n to store edge scores

The algorithm is efficient due to its linear nature. Both passes over the data scale directly with n, and no nested iteration is required.

Test Cases

# test cases
sol = Solution()

assert sol.edgeScore([1,0,0,0,0,7,7,5]) == 7  # example 1
assert sol.edgeScore([2,0,0,2]) == 0          # example 2
assert sol.edgeScore([1,2,3,4,0]) == 0        # cycle, all equal incoming scores
assert sol.edgeScore([1,0]) == 0              # smallest graph, two nodes
assert sol.edgeScore([1,1,1,1]) == 1          # all point to same node
Test Why
[1,0,0,0,0,7,7,5] Standard case, multiple edge scores
[2,0,0,2] Tie-breaking by smallest index
[1,2,3,4,0] Cycle where edge scores are equal
[1,0] Minimal graph with two nodes
[1,1,1,1] All nodes point to a single node, tests accumulation

Edge Cases

One important edge case is a graph where multiple nodes share the same maximum edge score. The solution handles this by comparing indices and returning the smallest index.

Another edge case is a minimal graph with only two nodes. The algorithm must correctly handle the accumulation and tie-breaking with minimal data.

Finally, a graph where a node has no incoming edges must not be chosen as the result. The solution correctly initializes scores to zero and only updates them when nodes point to a target, ensuring nodes without incoming edges are correctly ignored unless they have the highest score (zero in case all nodes are isolated).