Google | Phone screen | Closest XY pair in a grid
10779

Give a gird, and there are X and Y in this grid. find the shortest distance between X and Y.

Example 1:

Input:
[[X,0,0],
 [0,Y,0],
 [X,Y,0]] 
Output: 1

Example 2:

Input:
[[X,X,0],
 [0,0,Y],
 [Y,0,0]] 
Output: 2
Solution

Java Multisource BFS: https://leetcode.com/playground/cbPfw8Zd
Time complexity: O(r * c).
Space complexity: O(r * c).

Follow-up:
Output coordinates of the closet XY pair.

Comments (15)