Find Closest Node to Given Two Nodes | Leetcode 2359

class Solution {
    #define pii pair<int,int>
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        int n=edges.size();
        /*
            dist[A][0]=X: Distance from node1(source1) to 'node A' is X
            dist[A][1]=Y: Distance from node2(source2) to 'node A' is Y
        */
        vector<vector<int>> dist(n,vector<int>(2,-1));
        dist[node1][0]=0;
        dist[node2][1]=0;
        
        //Step-1: Multi-Source BFS to calculate distance of all nodes from node1 & node2
        queue<pii> q;
        q.push({node1,0});
        q.push({node2,1});
        while(!q.empty()){
            auto& [curr,type] = q.front();
            
            if(edges[curr]!=-1 and dist[edges[curr]][type]==-1){
                dist[edges[curr]][type] = 1 + dist[curr][type];
                q.push({edges[curr],type});
            }
            q.pop();
        }

        //Step-2: Minimize the max-distance of a node from node1 & node2 and track the meeting point
        int meeting_point = INT_MAX;
        int meeting_distance = INT_MAX;
        for(int i=0;i<n;++i){
            if(dist[i][0]!=-1 and dist[i][1]!=-1){
                int curr_dist = max(dist[i][0],dist[i][1]);
                if(curr_dist < meeting_distance){
                    meeting_distance = curr_dist;
                    meeting_point = i;
                }
            }
        }
        return meeting_point==INT_MAX?-1:meeting_point;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[][] dist = new int[n][2];
        for (int[] row : dist) {
            Arrays.fill(row, -1);
        }
        dist[node1][0] = 0;
        dist[node2][1] = 0;
        
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{node1, 0});
        q.offer(new int[]{node2, 1});
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int node = curr[0];
            int type = curr[1];
            
            int neighbor = edges[node];
            if (neighbor != -1 && dist[neighbor][type] == -1) {
                dist[neighbor][type] = dist[node][type] + 1;
                q.offer(new int[]{neighbor, type});
            }
        }
        
        int meetingPoint = -1;
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (dist[i][0] != -1 && dist[i][1] != -1) {
                int currDistance = Math.max(dist[i][0], dist[i][1]);
                if (currDistance < minDistance) {
                    minDistance = currDistance;
                    meetingPoint = i;
                }
            }
        }
        return meetingPoint;
    }
}

#Python
from collections import deque

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        dist = [[-1, -1] for _ in range(n)]
        dist[node1][0] = 0
        dist[node2][1] = 0
        
        q = deque()
        q.append((node1, 0))
        q.append((node2, 1))
        
        while q:
            curr, typ = q.popleft()
            neighbor = edges[curr]
            if neighbor != -1 and dist[neighbor][typ] == -1:
                dist[neighbor][typ] = dist[curr][typ] + 1
                q.append((neighbor, typ))
        
        meeting_point = -1
        min_distance = float('inf')
        for i in range(n):
            if dist[i][0] != -1 and dist[i][1] != -1:
                curr_distance = max(dist[i][0], dist[i][1])
                if curr_distance < min_distance:
                    min_distance = curr_distance
                    meeting_point = i
        return meeting_point
*/