Arrow Path Matrix Check | Dataford Interview Questions

Your question is Arrow Path Matrix Check. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

A GoDaddy website-navigation prototype represents each location in a grid with a directional arrow. Given a rectangular matrix containing arrows, a start coordinate, and one target cell, determine whether following the arrows from the start eventually reaches the target.

Return True only if the path reaches T. Return False if it leaves the matrix or revisits any cell, which indicates a cycle. The target cell is terminal and does not contain an arrow.

Formal Specification

Implement can_reach_target(grid, start).

grid is a non-empty rectangular list of equal-length strings.
Each character is one of U, D, L, R, or T.
U, D, L, and R direct movement to the adjacent cell in that direction.
T is the unique target cell.
start is a two-element list [row, column] identifying an arrow cell.
Return a boolean.

Your solution must handle grids large enough that recursive DFS could overflow Python's call stack. Aim for linear time in the number of cells visited.

Constraints

1 <= rows, columns <= 10^3
rows * columns <= 10^6
Each row has the same number of columns
Each character is one of U, D, L, R, or T
There is exactly one T cell
start identifies an arrow cell
Arrows may point outside the matrix

Function Signature

def can_reach_target(grid, start):