LeetCode 2737: Find the Closest Marked Node Solution

Master LeetCode problem 2737 (Find the Closest Marked Node), 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.

2737. Find the Closest Marked Node

Medium

Array Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation:

The problem asks us to find the node in a graph that is marked as true and is closest to a given query node. We can solve this problem by performing a Breadth First Search (BFS) from the query node to find the closest marked node.

Algorithm:

Create an adjacency list to represent the graph.
Perform BFS starting from the query node.
Keep track of the distance from the query node to each node visited during BFS.
Whenever we encounter a marked node during BFS, return that node as the closest marked node.

Time Complexity:

The time complexity of this approach is O(V + E), where V is the number of nodes and E is the number of edges in the graph.

Space Complexity:

The space complexity is O(V), where V is the number of nodes in the graph.

: :

Solution Code

class Solution {
    public int findClosestNode(int n, int[][] edges, boolean[] marked, int query) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(query);
        boolean[] visited = new boolean[n];
        visited[query] = true;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (marked[curr]) {
                    return curr;
                }
                for (int neighbor : graph.get(curr)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2737 (Find the Closest Marked Node)?

This page provides optimized solutions for LeetCode problem 2737 (Find the Closest Marked Node) 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 2737 (Find the Closest Marked Node)?

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

Can I run code for LeetCode 2737 on DevExCode?

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

Back to LeetCode Solutions