Juspay OA 2023 - Maximum Weight Node in a Maze

Problem Description:

You are given a maze with N cells, where each cell may have multiple entry points but no more than one exit. The cells are numbered from 0 to N-1.

The task is to find the node with the maximum weight. The weight of a node is defined as the sum of all the node numbers that point to that particular node.

Input Format:

1. The first line contains an integer N, the number of cells.
2. The second line contains N integers representing the Edge[] array. Here:
   • Edge[i] denotes the cell number that can be reached from cell i.
   • If Edge[i] is -1, it means that cell i has no exit (i.e., it does not point to any other cell).

Output Format:

• Output the integer representing the node number with the maximum weight. If there are multiple nodes with the same maximum weight, output the node with the largest number.

Constraints:

• 1 <= N <= 10^5

Example Input:

23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

Example Output:

22

Explanation:

In the input, cell 22 is pointed to by cells 17, 18, 19, 20, and 21, giving it the highest weight of ( 17 + 18 + 19 + 20 + 21 = 95 ). Therefore, the output is cell 22.