You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node ed

closestMeetingNode.js

/**
 * Finds the closest meeting node between two starting nodes in a directed graph.
 * 
 * @param {number[]} edges - Array representing directed edges of the graph.
 * @param {number} node1 - First starting node.
 * @param {number} node2 - Second starting node.
 * @return {number} - The closest meeting node or -1 if no valid meeting node exists.
 */

// Function to initialize an adjacency list representation of the graph
const initializeGraph = (n) => {
    let graph = Array.from({ length: n }, () => []); // Creates an array of empty lists
    return graph;
};

var closestMeetingNode = function(edges, node1, node2) {
    let n = edges.length;
    let graph = initializeGraph(n);

    // Step 1: Build the graph adjacency list
    for (let i = 0; i < n; i++) {
        if (edges[i] !== -1) {
            graph[i].push(edges[i]); // Connect node i to edges[i] if valid
        }
    }

    // Step 2: Calculate shortest distances from node1 and node2 using BFS
    let distFromNode1 = bfs(graph, node1);
    let distFromNode2 = bfs(graph, node2);

    let candidates = [];

    // Step 3: Find valid nodes that both node1 and node2 can reach
    for (let i = 0; i < n; i++) {
        if (distFromNode1[i] !== Number.MAX_SAFE_INTEGER && distFromNode2[i] !== Number.MAX_SAFE_INTEGER) {
            // Store max distance of both nodes reaching this point, along with the node index
            candidates.push([Math.max(distFromNode1[i], distFromNode2[i]), i]);
        }
    }

    // Step 4: Sort candidates based on shortest maximum distance, then by smallest index
    candidates.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0]; // Prioritize smaller max distances
        return a[1] - b[1]; // If same max distance, prioritize smaller index
    });

    // Step 5: Return the best meeting node or -1 if none exists
    return candidates.length ? candidates[0][1] : -1;
};

// BFS function to determine shortest distance from a starting node to all other nodes
const bfs = (graph, start) => {
    let n = graph.length;
    let distance = Array(n).fill(Number.MAX_SAFE_INTEGER); // Initialize distances to a large number
    let queue = [start];

    distance[start] = 0;

    while (queue.length) {
        let current = queue.shift(); // Get next node to process

        for (const neighbor of graph[current]) {
            if (distance[neighbor] > distance[current] + 1) {
                distance[neighbor] = distance[current] + 1; // Update shortest path
                queue.push(neighbor);
            }
        }
    }

    return distance;
};