Shortest Travel Time in a Grid with Traffic Lights
Updated
Problem statement
You are given an m x n grid grid that represents a road network. Each cell holds one of three values:
0(free road): the car can drive into this cell at any time.1(obstacle): the car can never enter this cell.2(traffic light): the car can enter this cell only while its light is green. Every light is green exactly at the timesT,2T,3T, and so on, and red at every other time.
The car starts at (startRow, startCol) at time 0 and wants to reach (endRow, endCol). In one move the car goes up, down, left, or right to a cell inside the grid, and each move takes 1 unit of time. A move into a traffic-light cell is allowed only if it ends at a green time. When the light ahead is red, the car waits in its current cell until it can make that move. The car may wait in its current cell for any whole number of time units, and leaving a traffic-light cell does not need a green light.
Return the minimum time for the car to reach the destination. If the destination is unreachable, return -1.
Function
shortestTravelTime(grid: int[][], T: int, startRow: int, startCol: int, endRow: int, endCol: int) → intExamples
Example 1
grid = [[0,2,0],[0,1,0],[0,0,0]]T = 3startRow = 0startCol = 0endRow = 0endCol = 2return = 4- The light at
(0, 1)is green at times3,6,9and so on. - Through the light: wait at
(0, 0)until time2, enter the light at time3, then reach(0, 2)at time4. - Around the obstacle:
(1, 0),(2, 0),(2, 1),(2, 2),(1, 2),(0, 2)takes6moves. - The fastest time is
4.
Example 2
grid = [[0,1],[1,0]]T = 2startRow = 0startCol = 0endRow = 1endCol = 1return = -1- Both neighbors of
(0, 0)are obstacles, so the car can never leave its start. - The destination is unreachable, so the answer is
-1.
Example 3
grid = [[0,0,0,2]]T = 5startRow = 0startCol = 0endRow = 0endCol = 3return = 5- The car reaches
(0, 2)at time2. - The destination
(0, 3)is a light, and it is green only at times5,10and so on. - The car waits at
(0, 2)until time4and enters the destination at time5.
Constraints
m == grid.lengthandn == grid[i].length1 <= m, n <= 100grid[i][j]is0,1, or2.1 <= T <= 10000 <= startRow, endRow < m0 <= startCol, endCol < ngrid[startRow][startCol] != 1andgrid[endRow][endCol] != 1
More Waymo Phone Screen questions
- Fixed-Order Task Run Time With CooldownPHONE SCREEN · Seen Oct 2026
- Reorderable Task Scheduler With CooldownPHONE SCREEN · Seen Oct 2026
- Island Area and Water BoundaryPHONE SCREEN · Seen Sep 2026
- Vehicle Maintenance Event ReadinessPHONE SCREEN · Seen Sep 2026
- Obstacle-Aware Return to OriginPHONE SCREEN · Seen Sep 2026
- Shortest Paths to Multiple TargetsPHONE SCREEN · Seen Sep 2026
- Deterministic Depth-First Graph TraversalPHONE SCREEN · Seen Sep 2026
- Shortest Distance from All BuildingsPHONE SCREEN · Seen Sep 2026
- Fixed-Range Frequency CountPHONE SCREEN · Seen Aug 2026
- Insert an Employee into an Organization HierarchyPHONE SCREEN · Seen Aug 2026
Similar questions at other companies
- Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Shortest Path with Directional Move CostsThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Maximum-Clearance Path From a PointGoogle · PHONE SCREENGoogle interview questions
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Minimum-Cost Path Through a Weighted GridVisa · OAVisa interview questions
- Grid ExplorationIMC Trading · OAIMC Trading interview questions
- Cookie Monster Minimum Arrival TimeIntuit · OAIntuit interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions