FastPrepDistance to the Nearest Taxi in a Grid

Distance to the Nearest Taxi in a Grid

Google logoGoogle● MediumNEW GRADPHONE SCREEN
Learn

Problem statement

A rectangular city grid contains taxis marked 'T' and ordinary cells marked '.'. Movement between cells is allowed up, down, left, and right.

Return a matrix where each cell contains its minimum number of moves to any taxi. A taxi cell has distance zero.

Function

nearestTaxiDistances(city: String[]) → int[][]

Examples

Example 1

city = ["T..","...","..T"]return = [[0,1,2],[1,2,1],[2,1,0]]

Distances expand from both taxis at once.

Example 2

city = [".T."]return = [[1,0,1]]

The one-row grid is symmetric around the taxi.

Example 3

city = ["T.",".."]return = [[0,1],[1,2]]

Each move changes Manhattan distance by one.

Constraints

  • 1 <= city.length, city[i].length <= 1000.
  • Every row has the same length.
  • Every character is 'T' or '.'.
  • At least one taxi is present.
  • The grid has at most 200000 cells.

More Google problems

See Google hiring insights
public int[][] nearestTaxiDistances(String[] city) {
    // Write your code here.
}
city["T..","...","..T"]
expected[[0,1,2],[1,2,1],[2,1,0]]
Checking account…