1
$\begingroup$

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector.

[[1, 1, 0],
 [0, 0, 0],  
 [0, 0, 0]]

should return

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

Basic BFS: ( approach-1)

If there are N elements in the matrix, one could do BFS starting every house to solve this. The worst case complexity of this approach is: Worst number of BFSes * O(E+V), where E is the number of edges in the matrix and V number of nodes = N * O(N + 4N) as number of edges is a constant factor of 4N. Time complexity: O(N*N)

multi-source BFS (approach-2)

  • Initialize the queue with all nodes (i, j) where i is the row number and j is the column for all stores. For each node (i, j) in the queue also store its corresponding (si, sj) node for the store that gives it the minimum square of euclidean distance (call it sqDist). For each store node (i, j), (si, sj) would be same as (i, j)

  • Initialize the distance answer that we are looking for each house with -1

  • During multi-source BFS, for a node (i, j) and it's best store (si, sj) in the queue, look at each of 8 adjacent nodes (since it's euclidean distance, we need to consider all 8 nodes not only 4 of left, right, top, down). If the current distance value for any of those nodes (nexti, nextj) is > the sqDist if (si, sj) is chosen as the best store for (nexti, nextj), then

    • update distance of (nexti, nextj) with the lower value
    • add (nexti,nextj) along with its best store as (si, sj) to the queue
  • Keep doing this until queue is empty

My question:

1) why does this work? Since we're looking at euclidean distance it's possible that (nexti, nextj) may not be added to the queue (or have their distance updated) for a certain (si, sj) but that (si, sj) node may still update the distance for nodes that are farther to it than (nexti, nextj) due to nature of euclidean distance. So (si, sj) may still need to be in the queue. How does this solution work inspite of this issue or what's the intuitive conceptual idea of why this works despite this issue as it's not obvious?

2) What's the time complexity?

it seems in the worst case you could add a node in the queue N times. So it becomes N * O(N *4N) where 4N is the number of edges in the matrix. So is it not any better than doing BFS individually for each house?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.