Skip to main content
Talentd

Find the Closest Marked Node - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGraphHeap (Priority Queue)Shortest Path8 min read
Practice this problem

Problem Statement

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 <= 500
  • 1 <= edges.length <= 104
  • edges[i].length = 3
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • 1 <= edges[i][2] <= 106
  • 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.

Approach Overview

Problem 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.

Solution

First, we construct an adjacency matrix g based on the edge information provided in the problem, where g[i][j] represents the distance from node i to node j. If such an edge does not exist, then g[i][j] is positive infinity.

Then, we can use Dijkstra's algorithm to find the shortest distance from the starting point s to all nodes, denoted as dist.

Finally, we traverse all the marked nodes and find the marked node with the smallest distance. If the distance is positive infinity, we return -1.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of nodes.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS (Unit Weights)O(V + E)O(V)When all edges have equal weight (typically 1)
Standard Dijkstra's AlgorithmO(E log V)O(V)General weighted graphs where all distances must be computed
Early-Stopping DijkstraO(E log V)O(V)Best choice when you only need the closest marked node

Video Solution

2737. Find the Closest Marked Node - Week 4/5 Leetcode March Challenge • Programming Live with Larry • 197 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Find the Closest Marked Node with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays