Is Find the Closest Marked Node easy or hard?

Find the Closest Marked Node is generally rated Medium difficulty. The graph modeling is straightforward, but the key step is recognizing that it requires a shortest path algorithm with weighted edges. Once you identify Dijkstra's algorithm and implement the priority queue correctly, the solution becomes manageable.

Find the Closest Marked Node Python/Java solution

The typical implementation builds an adjacency list, initializes a distance array with infinity, and pushes (0, startNode) into a priority queue. Then run Dijkstra's relaxation process until the heap is empty or a marked node is reached. The same algorithm translates cleanly across Python (heapq), Java (PriorityQueue), C++, Go, and TypeScript.

How to solve Find the Closest Marked Node in O(E log V)?

Run Dijkstra's algorithm from the start node. Maintain a distance array and a min-heap storing (distance, node). When you pop a node from the heap, check if it is marked; if so, return the distance immediately. Otherwise relax all outgoing edges and push updated distances into the heap.

What is the best approach for Find the Closest Marked Node?

The best approach is Dijkstra's algorithm using a min-heap (priority queue). It computes the shortest distance from the start node to all reachable nodes in O(E log V) time. You can optimize it further by stopping as soon as a marked node is popped from the heap, since Dijkstra guarantees that this distance is already minimal.

Is Find the Closest Marked Node asked at Google/Amazon/Meta?

Problems based on shortest path algorithms like Dijkstra frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants include finding the closest facility, shortest route in a weighted graph, or minimum distance to a target set of nodes. Recognizing when to apply Dijkstra is a common interview expectation.

What data structure is used in Find the Closest Marked Node?

The core data structure is a min-heap priority queue used by Dijkstra's algorithm. It always extracts the node with the smallest tentative distance. The algorithm also uses an adjacency list to represent the graph and an array to track the best known distance to each node.

What is the time complexity of Find the Closest Marked Node?

Using Dijkstra's algorithm with a priority queue, the time complexity is O(E log V), where E is the number of edges and V is the number of nodes. Each edge relaxation may push an entry into the heap, and heap operations take logarithmic time. The space complexity is O(V) for the distance array and visited tracking.

Description Hints 3 Solution Video 7:51

2737. Find the Closest Marked Node

Medium65.4% acceptancePremium elsewhere, free here

You are given a positive integer n which is the number of nodes of a 0-indexed directed weighted graph and a 0-indexed 2D array edges where edges[i] = [u_i, v_i, w_i] indicates that there is an edge from node u_i to node v_i with weight w_i.

You are also given a node s and a node array marked; your task is to find the minimum distance from s to any of the nodes in marked.

Return an integer denoting the minimum distance from s to any node in marked or -1 if there are no paths from s to any of the marked nodes.

Example 1:

Input: n = 4, edges = [[0,1,1],[1,2,3],[2,3,2],[0,3,4]], s = 0, marked = [2,3]
Output: 4
Explanation: There is one path from node 0 (the green node) to node 2 (a red node), which is 0->1->2, and has a distance of 1 + 3 = 4.
There are two paths from node 0 to node 3 (a red node), which are 0->1->2->3 and 0->3, the first one has a distance of 1 + 3 + 2 = 6 and the second one has a distance of 4.
The minimum of them is 4.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]], s = 1, marked = [0,4]
Output: 3
Explanation: There are no paths from node 1 (the green node) to node 0 (a red node).
There is one path from node 1 to node 4 (a red node), which is 1->3->4, and has a distance of 1 + 2 = 3.
So the answer is 3.

Example 3:

Input: n = 4, edges = [[0,1,1],[1,2,3],[2,3,2]], s = 3, marked = [0,1]
Output: -1
Explanation: There are no paths from node 3 (the green node) to any of the marked nodes (the red nodes), so the answer is -1.

Constraints:

2 <= n <= 500
1 <= edges.length <= 10⁴
edges[i].length = 3
0 <= edges[i][0], edges[i][1] <= n - 1
1 <= edges[i][2] <= 10⁶
1 <= marked.length <= n - 1
0 <= s, marked[i] <= n - 1
s != marked[i]
marked[i] != marked[j] for every i != j
The graph might have repeated edges.
The graph is generated such that it has no self-loops.

Topics

Hints open one at a time

Hint 1

Find the distance from s to all nodes.

Hint 2

You can use Dijkstra to find them.

Hint 3

Find the minimum distance between marked nodes.

7:51

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

4
[[0,1,1],[1,2,3],[2,3,2],[0,3,4]]
0
[2,3]

Input

5
[[0,1,2],[0,2,4],[1,3,1],[2,3,3],[3,4,2]]
1
[0,4]

Input

4
[[0,1,1],[1,2,3],[2,3,2]]
3
[0,1]

Your code is saved on this device.Solution