Determine if a Cell Is Reachable at a Given Time

Determine if a Cell Is Reachable at a Given Time

What is this problem about?

In the Determine if a Cell Is Reachable at a Given Time coding problem, you are given a starting point $(sx, sy)$, a target point $(fx, fy)$, and a time limit $t$. In each second, you must move to any of the 8 adjacent cells (including diagonals). You need to determine if it is possible to be exactly at the target cell after exactly $t$ seconds.

Why is this asked in interviews?

Google asks this to test your ability to simplify geometric problems. While it might look like a BFS or pathfinding problem, the "8-way movement" makes it a simple distance calculation problem. It evaluations your understanding of Chebyshev distance and your ability to identify edge cases where the path might be too short to consume enough time.

Algorithmic pattern used

This problem uses Coordinate Geometry (Chebyshev Distance).

1. Calculate the minimum distance: minDist = max(abs(sx - fx), abs(sy - fy)).
2. If minDist > t, it is impossible to reach the target in time.
3. Edge Case: If the start and target are the same $(sx == fx, sy == fy)$, you can stay put or move and come back. However, you can't be back at the start in exactly 1 second (since you must move). So if $sx == fx$ and $sy == fy$, and $t == 1$, return false.
4. Otherwise, return true.

Example explanation

Start: (1, 1), Target: (3, 3), $t = 2$.

1. max(abs(3-1), abs(3-1)) = 2.
2. minDist (2) <= t (2). Result: true. Start: (1, 1), Target: (1, 1), $t = 1$.
3. Same cell, but $t=1$. You move out and can't get back in 1 second. Result: false.

Common mistakes candidates make

• Using BFS: Trying to use BFS will result in a Time Limit Exceeded error because the coordinates can be up to $10^9$.
• Missing the $t=1$ Edge Case: Forgetting that if you are at the target and have 1 second left, you must move away and cannot return in time.
• Manhattan Distance: Incorrectly using $|dx| + |dy|$, which only applies to 4-way movement.

Interview preparation tip

Always look at the movement rules first. 4-way movement $\implies$ Manhattan Distance. 8-way movement $\implies$ Chebyshev Distance (Maximum of $dx$ or $dy$). Euclidean distance $\implies$ Straight line.