Determine if a Cell Is Reachable at a Given Time

Med

#2548Time: O(8^t). At each step `k`, we can reach up to `8^k` new cells.Space: O(8^t). The queue and visited set can grow exponentially.

Patterns

Math

Prompt

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 <= 10⁹
0 <= t <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process of moving on the grid step by step. We can use a Breadth-First Search (BFS) to explore all possible cells reachable at each second, from 1 to t. We start at (sx, sy) at time 0. At each second, we explore all 8 adjacent cells from the cells we could reach in the previous second. If at exactly time t, one of the reachable cells is (fx, fy), we return true.

Algorithm

Initialize a queue and add the starting state (sx, sy, 0).
Initialize a set visited to store (x, y, time) tuples to avoid redundant exploration. Add (sx, sy, 0) to visited.
While the queue is not empty:
- Dequeue the current state (x, y, time).
- If time == t:
  - If x == fx and y == fy, return true.
  - Continue to the next state in the queue.
- If time > t, stop exploring this path.
- For each of the 8 neighbors (nx, ny) of (x, y):
  - If (nx, ny, time + 1) is not in visited:
    - Add (nx, ny, time + 1) to visited.
    - Enqueue (nx, ny, time + 1).
If the loop finishes, it means (fx, fy) was not reached at exactly time t. Return false.

Walkthrough

The state in our search can be represented by (x, y, time). We start with a queue containing the initial state (sx, sy, 0). We also need a way to keep track of visited states (x, y, time) to avoid cycles and redundant work. A hash set is needed due to the large coordinate values.

The BFS proceeds level by level, where each level corresponds to one second of time. In each step, we dequeue a state (curr_x, curr_y, curr_time). If curr_time == t, we check if we are at the destination. If curr_time < t, we generate all 8 adjacent cells and enqueue them for the next time step if they haven't been visited at that specific time. This approach is not feasible given the constraints t <= 10^9 because the number of reachable cells grows exponentially with time.

Complexity

Time

O(8^t). At each step `k`, we can reach up to `8^k` new cells.

Space

O(8^t). The queue and visited set can grow exponentially.

Trade-offs

Pros

Conceptually simple and directly models the problem statement.

Cons

Extremely inefficient. The time and space complexity are exponential in t, making it infeasible for the given constraints.
t can be up to 10^9, so a simulation is impossible.
Storing visited states with large coordinates requires a hash-based set, which has overhead.

Instead of simulating the movement, we can solve this problem by analyzing the properties of movement on the grid. The key insight is to determine the minimum time required to travel between the start and end cells and then consider how any extra time can be spent.

Algorithm

Calculate the horizontal distance dx = |sx - fx|.
Calculate the vertical distance dy = |sy - fy|.
Check for the special case where the start and end points are the same (dx == 0 and dy == 0).
- If they are the same, return true if t is not equal to 1, and false otherwise. This is because we must move each second, so we can't stay at the same spot at t=1. For t=0 we are already there, and for t>=2 we can move away and come back.
If the points are different, calculate the minimum time required, which is the Chebyshev distance: min_time = max(dx, dy).
Return true if the given time t is greater than or equal to min_time, and false otherwise. Any time t >= min_time is achievable.

Walkthrough

The minimum number of moves to get from (sx, sy) to (fx, fy) is determined by the Chebyshev distance, which is max(|sx - fx|, |sy - fy|). This is because in one move (one second), we can cover at most one unit of distance in the x-direction and one unit in the y-direction (with a diagonal move). To cover a total horizontal distance of dx = |sx - fx| and vertical distance of dy = |sy - fy|, we need at least max(dx, dy) moves. Let this be min_time.

The problem can be broken down into two main cases:

Start and Finish cells are the same (sx = fx, sy = fy):
- In this case, dx = 0 and dy = 0, so min_time = 0.
- If t = 0, we are already at the destination. It's possible.
- If t = 1, we must move to an adjacent cell, so we cannot be at the starting cell. It's impossible.
- If t >= 2, we can spend the time by moving to an adjacent cell and then moving back. This takes 2 seconds. It's possible for any t except t=1.
Start and Finish cells are different:
- The minimum time required is min_time = max(dx, dy).
- If the given time t is less than min_time, it's impossible to reach the destination.
- If t >= min_time, we can always reach the destination. We can arrive in min_time seconds using an optimal path. Any extra time t - min_time can be "wasted" by taking small detours or moving back-and-forth from the destination. Thus, if t >= min_time, it's always possible.

Combining these observations gives a simple and efficient algorithm.

1class Solution {2    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {3        int dx = Math.abs(sx - fx);4        int dy = Math.abs(sy - fy);5 6        if (dx == 0 && dy == 0) {7            // If start and end are the same, we can't reach in exactly 1 second8            // because we must move. For any other time t != 1, it's possible.9            return t != 1;10        }11 12        int minTime = Math.max(dx, dy);13        14        // If we are not at the same cell, we must take at least minTime steps.15        return t >= minTime;16    }17}

Complexity

Time

O(1). The solution involves a few arithmetic operations and comparisons, which take constant time.

Space

O(1). No extra space is used that depends on the input size.

Trade-offs

Pros

Extremely efficient with constant time and space complexity.
Handles all edge cases correctly.
Works for the large constraints given in the problem.

Cons

The logic is not immediately obvious and requires some mathematical reasoning about grid movement.

Solutions

Solution

1public class Solution {2    public bool IsReachableAtTime(int sx, int sy, int fx, int fy, int t) {3        if (sx == fx && sy == fy) return t != 1;4        return Math.Max(Math.Abs(sx - fx), Math.Abs(sy - fy)) <= t;5    }6}

1class Solution {2public3  boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {4    if (sx == fx && sy == fy) {5      return t != 1;6    }7    int dx = Math.abs(sx - fx);8    int dy = Math.abs(sy - fy);9    return Math.max(dx, dy) <= t;10  }11}

1class Solution:2    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool: if sx == fx and sy == fy: return t != 1 dx = abs(sx - fx) dy = abs(sy - fy) return max(dx, dy) <= t

1class Solution {2public:3  bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {4    if (sx == fx && sy == fy) {5      return t != 1;6    }7    int dx = abs(fx - sx), dy = abs(fy - sy);8    return max(dx, dy) <= t;9  }10};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem