We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Node With Highest Edge Score

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each node has exactly one outgoing edge, forming a directed graph.
  • The edge score for each node can be calculated by summing the indices of all nodes that point to it.
  • A single pass through the edges can calculate the scores efficiently using a hash table or an array.
  • The node with the highest edge score needs to be tracked during the calculation.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will utilize an array to keep track of the edge scores for each node. We will iterate through the edges array, for each node i, we will add i to the score of the node that i points to (edges[i]). After calculating all scores, we will find the node with the maximum score. If there are ties, we will select the node with the smallest index.

Code Solutions

def node_with_highest_edge_score(edges):
    n = len(edges)
    score = [0] * n  # Initialize scores for each node

    # Calculate edge scores
    for i in range(n):
        score[edges[i]] += i

    # Find the node with the highest edge score
    max_score = -1
    result_node = -1
    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
← Back to All Questions