Watch 3 video solutions for Find the Closest Marked Node, a medium level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by Programming Live with Larry has 196 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] = [ui, vi, wi] indicates that there is an edge from node ui to node vi with weight wi.
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 <= 5001 <= edges.length <= 104edges[i].length = 30 <= edges[i][0], edges[i][1] <= n - 11 <= edges[i][2] <= 1061 <= marked.length <= n - 10 <= s, marked[i] <= n - 1s != marked[i]marked[i] != marked[j] for every i != jProblem Overview: You are given a directed weighted graph, a start node s, and a list of marked nodes. The goal is to compute the minimum distance from s to any marked node. If no marked node is reachable, return -1. This is a classic single-source shortest path problem where the target is any node in a subset.
Approach 1: BFS for Unit Weights (O(V + E) time, O(V) space)
If every edge weight is exactly 1, the graph effectively behaves like an unweighted graph. In that case, a standard BFS starting from s finds the shortest path to all nodes. You push neighbors into a queue and track distance by level. As soon as a marked node is dequeued, you have the minimum distance. This approach only works when weights are uniform and is commonly discussed when learning graph traversal.
Approach 2: Standard Dijkstra's Algorithm (O(E log V) time, O(V) space)
For general weighted graphs, the correct solution is Dijkstra's Algorithm. Maintain a distance array initialized to infinity and a min-heap priority queue storing (distance, node). Start by pushing (0, s). Repeatedly pop the smallest distance node, relax all outgoing edges, and update neighbor distances when a shorter path is found. After the algorithm finishes, compute the minimum distance among all marked nodes. This approach relies on a heap (priority queue) and is the standard solution for weighted shortest path problems.
Approach 3: Early-Stopping Dijkstra (O(E log V) time, O(V) space)
You can optimize the previous approach by stopping as soon as the first marked node is extracted from the priority queue. Dijkstra guarantees that the node popped from the heap has the globally smallest distance among all unvisited nodes. If that node is marked, its distance is already the minimum possible among all marked nodes. This avoids exploring the entire graph when the closest marked node appears early in the search. The implementation is almost identical to standard Dijkstra, with a quick check after each heap pop.
Recommended for interviews: Dijkstra's algorithm with early stopping. Interviewers expect you to recognize that this is a weighted single-source shortest path problem. Mentioning BFS for unit weights shows conceptual depth, but implementing Dijkstra with a priority queue demonstrates practical problem-solving skill and knowledge of graph algorithms.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS (Unit Weights) | O(V + E) | O(V) | When all edges have equal weight (typically 1) |
| Standard Dijkstra's Algorithm | O(E log V) | O(V) | General weighted graphs where all distances must be computed |
| Early-Stopping Dijkstra | O(E log V) | O(V) | Best choice when you only need the closest marked node |