← All questions
Coding

Find The Closest Marked Node

Asked atMicrosoft
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

The number of nodes in a 0-indexed **directed **weighted graph, represented by the positive integer n, and the edges of a 0-indexed 2D array, where edges[i] = [ui, vi, wi], show that there is an directed edge from node ui to node vi with weight wi, are provided to you.

A node s and a node array **marked **are also provided to you; your job is to determine the smallest distance between s and any of the nodes in marked.

If there are no paths from s to any of the marked nodes, return -1; otherwise, return an integer representing the minimum distance between s and any node in marked.

Input : n = 5, s = 0, edges = [ [0, 1, 3], [0, 2, 4], [0, 3, 1], [0, 4, 2] ], marked = [1, 2, 3] **Output : **1 Explanation : The paths from node s (0) to marked nodes is as below : 0 to 1 -> 3 0 to 2 -> 4 0 to 3 -> 1 So the smallest distance is 1 i.e. from 0 to node 3.

Input : n = 5, s = 1, edges = [ [0, 1, 5], [0, 2, 4], [0, 3, 1], [0, 4, 2], [1, 2, 1], [2, 3, 1] ], marked = [3, 4] **Output : **2 Explanation : The paths from node s (1) to marked nodes is as below : 1 to 3 -> 1 + 1 -> 2. 1 to 4 -> -1 ( There is no path from 1 to 4). So the smallest distance is 2 i.e. from 1 to node 3.

Input : n = 5, s = 1, edges = [ [0, 1, 3], [0, 2, 4], [0, 3, 1], [0, 4, 2] ], marked = [2, 3, 4]

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

cpp

class Solution {
    public:
        int minimumDistance(int n, vector<vector<int>>& edges, int s, vector<int>& marked) {
            //your code goes here
        }
};

java

class Solution{
    public static int minimumDistance(int n, List<int[]> edges, int s, List<Integer> marked) {
        //your code goes here
    }
}

python

class Solution:
    def minimum_distance(n, edges, s, marked):
        #your code goes here

javascript

class Solution{
    minimumDistance(n, edges, s, marked) {
        //your code goes here
    }
}

csharp

class Solution {
    public int minimumDistance(int n, List<int[]> edges, int s, int[] marked) {
        //your code goes here
    }
}

go

func minimumDistance(n int, edges [][]int, s int, marked []int) int {
	// your code goes here
}
Stuck? Show a way to structure it+
  1. 01Clarify directedness, source, and whether there are many queries
  2. 02Build an adjacency list and a boolean marked array
  3. 03Run BFS in the direction that supports the query pattern
  4. 04Return the first target distance or -1

Reference answer

Then expect these follow-ups

  • How would this change for weighted edges?

    Tests: constraint adaptation

  • How would you answer many source queries?

    Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question