Juspay OA 2023 - Nearest Meeting Cell 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 (i.e., entry/exit points are unidirectional like valves). The cells are numbered from 0 to N-1.

You are tasked with finding the nearest meeting cell for two given cells C1 and C2 . A meeting cell is the first common cell that can be reached from both C1 and C2 by following the exits from each cell. If no such meeting cell exists, return -1.

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, where Edge[i] denotes the cell that can be reached from cell i. If Edge[i] is -1, it means cell i has no exit.
3. The third line contains two integers C1 and C2, representing the two starting cells for which you need to find the nearest meeting cell.

Output Format:

• Output the integer representing the nearest meeting cell (NMC). If no common meeting cell exists, return -1.

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
9 2

Example Output:

4

Explanation:

In this example:

• The cells are connected as per the Edge[] array.
• We need to find the nearest meeting cell that can be reached from both cell 9 and cell 2. The answer is cell 4, as it is the first common cell reachable from both starting cells.