Watch 10 video solutions for Determine if a Cell Is Reachable at a Given Time, a medium level problem involving Math. This walkthrough by codestorywithMIK has 3,206 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given four integers sx, sy, fx, fy, and a non-negative integer t.
In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.
Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.
A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.
Example 1:
Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6 Output: true Explanation: Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above.
Example 2:
Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3 Output: false Explanation: Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. Hence, we cannot reach cell (7, 3) at the third second.
Constraints:
1 <= sx, sy, fx, fy <= 1090 <= t <= 109Problem Overview: You start at cell (sx, sy) on an infinite grid and want to reach (fx, fy) exactly at time t. In one second you may move to any of the 8 neighboring cells (horizontal, vertical, or diagonal). The task is to determine whether the destination can be reached in exactly t moves.
Approach 1: Minimum Steps with Parity Check (O(1) time, O(1) space)
The key observation is that diagonal movement allows you to reduce both row and column distance at the same time. The minimum number of moves needed is the Chebyshev distance: max(|sx - fx|, |sy - fy|). If this minimum distance is greater than t, reaching the target is impossible. If the distance is less than or equal to t, you can usually spend extra moves by wandering around nearby cells.
There is one edge case: when the start and end cells are the same and t = 1. Any move must change the position, so returning to the same cell in exactly one step is impossible. For all other cases where t is at least the minimum distance, the destination is reachable. This constant‑time observation makes the problem a pure math reasoning exercise rather than a full search.
Approach 2: Simulation with BFS Algorithm (O(t²) time, O(t²) space)
A straightforward approach treats the grid as a graph where each cell connects to its eight neighbors. Starting from (sx, sy), perform a Breadth‑First Search (BFS) and expand all reachable cells level by level until time t. If the destination appears at exactly level t, return true.
Because the grid is infinite, BFS must be limited to cells that can possibly be reached within t moves, effectively a square region around the start. This leads to roughly O(t²) states in the worst case. While this approach models the movement rules directly and is easy to reason about, it is far slower than the mathematical observation.
Recommended for interviews: Interviewers expect the constant‑time math solution using Chebyshev distance. It shows you recognize the movement pattern of 8-direction grids and avoid unnecessary graph traversal. Discussing the BFS simulation first can demonstrate baseline reasoning, but the O(1) approach proves stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Minimum Steps with Parity Check (Math) | O(1) | O(1) | Best approach. Uses Chebyshev distance to compute the minimum moves directly. |
| Simulation with BFS | O(t²) | O(t²) | Useful for understanding grid movement or when deriving the mathematical shortcut. |