FastPrepDistances to the Nearest Infected Node
Problem · Graph

Distances to the Nearest Infected Node

Learn this problem
● MediumGoogle logoGoogleINTERNONSITE INTERVIEW
See Google hiring insights

Problem statement

You are given an undirected, unweighted graph with n nodes numbered from 0 to n - 1. The array infected contains the distinct nodes that are already infected.

Return an integer array distance of length n, where distance[v] is the minimum number of edges on a path from node v to any infected node. Return -1 for a node that cannot reach any infected node.

Function

nearestInfectedDistances(n: int, edges: int[][], infected: int[]) → int[]

Examples

Example 1

n = 7edges = [[0,1],[1,2],[2,3],[4,5]]infected = [0,3,5]return = [0,1,1,0,1,0,-1]

Nodes 0, 3, and 5 start at distance 0. Nodes 1, 2, and 4 are one edge from an infected node. Node 6 is isolated, so its distance is -1.

Example 2

n = 5edges = [[0,1],[1,2],[2,3],[3,4]]infected = [1,4]return = [1,0,1,1,0]

A shortest path may end at either infected source. Node 3, for example, is one edge from node 4.

Constraints

  • 1 <= n <= 200000
  • 0 <= edges.length <= 200000
  • Every row of edges is [u, v] with 0 <= u, v < n and u != v.
  • 1 <= infected.length <= n
  • All entries of infected are distinct valid node indices.

More Google problems

drafts saved locally
public int[] nearestInfectedDistances(int n, int[][] edges, int[] infected) {
    // write your code here
}
n7
edges[[0,1],[1,2],[2,3],[4,5]]
infected[0,3,5]
expected[0,1,1,0,1,0,-1]
checking account