Quick Overview

Find when simultaneous grid signals reach every target while blockers prevent propagation, including unreachable targets and empty target sets.

Find the Time for Grid Signals to Reach Every Target

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a rectangular city grid, return the earliest time at which every target has received a signal. All sources begin transmitting simultaneously at time zero. Each unit of time, a signal can spread one cell up, down, left, or right. Blockers prevent entry; all other cell types allow propagation. ### Input - `grid`: an array of equal-length strings containing `S` for a source, `B` for a blocker, `T` for a target, and `.` for an empty cell. ### Output Return the earliest time when all targets have received a signal. Return `-1` if any target is unreachable. ### Constraints and Edge Cases - For this practice version, the grid has between `1` and `200` rows and between `1` and `200` columns. - A signal may pass through a target or another source. - Sources do not need to wait for one another, and multiple signals do not interfere. - If there are no targets, return `0`. - If targets exist but there are no sources, return `-1`. - Diagonal movement is not allowed. ### Example 1 ```text grid = ["S.BT", ".B..", "T..S"] output = 2 ``` The bottom-left target receives a signal from the top-left source after two steps. The top-right target receives a signal from the bottom-right source after two steps. ### Example 2 ```text grid = ["SBT"] output = -1 ``` The blocker separates the only source from the target.

Overview: Find when simultaneous grid signals reach every target while blockers prevent propagation, including unreachable targets and empty target sets.

Read the full Google Software Engineer interview experience this question came from

Given a rectangular city grid, return the earliest time at which every target has received a signal. All sources begin transmitting simultaneously at time zero. Each unit of time, a signal can spread one cell up, down, left, or right. Blockers prevent entry; all other cell types allow propagation. ### Input - `grid`: an array of equal-length strings containing `S` for a source, `B` for a blocker, `T` for a target, and `.` for an empty cell. ### Output Return the earliest time when all targets have received a signal. Return `-1` if any target is unreachable. ### Constraints and Edge Cases - For this practice version, the grid has between `1` and `200` rows and between `1` and `200` columns. - A signal may pass through a target or another source. - Sources do not need to wait for one another, and multiple signals do not interfere. - If there are no targets, return `0`. - If targets exist but there are no sources, return `-1`. - Diagonal movement is not allowed. ### Example 1 ```text grid = ["S.BT", ".B..", "T..S"] output = 2 ``` The bottom-left target receives a signal from the top-left source after two steps. The top-right target receives a signal from the bottom-right source after two steps. ### Example 2 ```text grid = ["SBT"] output = -1 ``` The blocker separates the only source from the target.

Constraints

  • The rectangular grid has 1 through 200 equal-length rows and 1 through 200 columns, using only S, B, T and period.
  • Every source starts at time zero. Movement is orthogonal, takes one unit per edge, and may pass through sources and targets.
  • Blockers are not traversable; no removal or diagonal movement is permitted.
  • Return the latest first-arrival time over all targets, zero if there are no targets, and -1 if any target is unreachable.

Examples

Input: (['S.BT', '.B..', 'T..S'],)

Expected Output: 2

Explanation: Published sample 1: the two targets receive independent simultaneous arrivals of two steps from different sources.

Input: (['SBT'],)

Expected Output: -1

Explanation: Published sample 2: the blocker separates source and target.

Loading coding console...

Show the approach

Approach

Scan the grid and place every source into a single queue with distance zero. Then perform breadth-first search. When a cell is removed from the queue, enter each unseen orthogonal neighbor that is not a blocker, assign its distance as the current distance plus one, and append it. A moving queue index avoids shifting the remaining elements.

All sources are initialized before any propagation, so the breadth-first layers represent elapsed time from the nearest source rather than separate journeys from a selected source. At the first visit to a cell, no shorter route from any source can exist: such a route would reach it from an earlier layer. Conversely every reachable non-blocker cell is eventually visited through its path from a source. Targets and source cells are traversable, and signals do not delay or block one another.

If there are no targets, return zero immediately. Otherwise inspect every target after the search. An unseen target makes the answer -1; when all were reached, the largest recorded distance is the first time at which all targets have received a signal. With no sources the queue stays empty and every existing target remains unseen.

Each cell is queued at most once and has four possible neighbors, so the time and auxiliary space are O(R*C). Traversal is iterative even for long winding corridors. The full 200-by-200 domain has at most 40000 cells, making every finite shortest path at most 39999 steps; indices and distances fit signed 32-bit integers. The algorithm does not modify the grid.

Time complexity:
O(R*C) for one simultaneous multi-source breadth-first search and target scan.
Space complexity:
O(R*C) for distances, queued cells and target locations.