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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Node With Highest Edge Score

Number: 2455

Difficulty: Medium

Paid? No

Companies: Juspay

Problem Description

Given a directed graph with n nodes labeled from 0 to n - 1 where each node has exactly one outgoing edge represented by the array edges, the edge score for a node is defined as the sum of the labels of all nodes that point to it. The task is to compute the edge scores for all nodes and return the node with the highest edge score. If multiple nodes have the same highest score, return the one with the smallest index.

Key Insights

  • Every node i contributes its own index to the score of the node edges[i].
  • A single pass through the edges array is sufficient to accumulate the scores.
  • An additional pass through the scores helps determine the node with the maximum edge score.
  • In the case of a tie, the smallest index is returned.

Space and Time Complexity

Time Complexity: O(n) – We traverse the edges array once to compute scores and once more to find the maximum. Space Complexity: O(n) – An auxiliary array of size n is used to store the computed scores.

Solution

The solution uses an auxiliary array (or similar data structure) to maintain the cumulative score for each node. We iterate through the given edges list, adding each node's label (its index) to the score of the node it points to (edges[i]). After computing these scores, we perform a linear scan to find the node with the maximum score, ensuring that in the case of ties, the node with the smallest index is selected.

Code Solutions

# Define the function to find the node with the highest edge score
def edgeScore(edges):
    n = len(edges)  # Total number of nodes
    scores = [0] * n  # Initialize scores array with zeros

    # Build the edge scores array by adding the index of each node to the destination node's score
    for i, dest in enumerate(edges):
        scores[dest] += i

    # Find the node with the maximum edge score
    best_node = 0
    best_score = scores[0]
    for i in range(1, n):
        # Check if the current score is higher, or if equal, use the node with a smaller index.
        if scores[i] > best_score:
            best_score = scores[i]
            best_node = i

    return best_node

# Example usage:
edges = [1, 0, 0, 0, 0, 7, 7, 5]
print(edgeScore(edges))  # Expected output: 7
← Back to All Questions