LeetCode 2359: Find Closest Node to Given Two Nodes Solution

Master LeetCode problem 2359 (Find Closest Node to Given Two Nodes), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2359. Find Closest Node to Given Two Nodes

Medium

Depth-First Search Graph

Problem Explanation

Explanation

To solve this problem, we can perform a Breadth-First Search (BFS) starting from both node1 and node2. We keep track of the distance from each starting node to all other nodes. Then, we find the node that can be reached from both node1 and node2 with the minimum maximum distance.

Perform BFS from node1 and node2 to calculate the distances to all other nodes.
Find the common reachable node with the minimum maximum distance.
Return the index of the found node or -1 if no common reachable node exists.

Time Complexity: O(n) Space Complexity: O(n)

Solution Code

import java.util.*;

class Solution {
    public int findClosestNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            if (edges[i] != -1) {
                graph.get(i).add(edges[i]);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited1 = new boolean[n];
        boolean[] visited2 = new boolean[n];
        int[] dist1 = new int[n];
        int[] dist2 = new int[n];

        queue.offer(node1);
        visited1[node1] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int next : graph.get(curr)) {
                if (!visited1[next]) {
                    visited1[next] = true;
                    dist1[next] = dist1[curr] + 1;
                    queue.offer(next);
                }
            }
        }

        queue.clear();
        queue.offer(node2);
        visited2[node2] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int next : graph.get(curr)) {
                if (!visited2[next]) {
                    visited2[next] = true;
                    dist2[next] = dist2[curr] + 1;
                    queue.offer(next);
                }
            }
        }

        int minMaxDistance = Integer.MAX_VALUE;
        int result = -1;
        for (int i = 0; i < n; i++) {
            if (visited1[i] && visited2[i]) {
                int maxDist = Math.max(dist1[i], dist2[i]);
                if (maxDist < minMaxDistance) {
                    minMaxDistance = maxDist;
                    result = i;
                }
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2359 (Find Closest Node to Given Two Nodes)?

This page provides optimized solutions for LeetCode problem 2359 (Find Closest Node to Given Two Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2359 (Find Closest Node to Given Two Nodes)?

The time complexity for LeetCode 2359 (Find Closest Node to Given Two Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2359 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2359 in Java, C++, or Python.

Back to LeetCode Solutions