Problem Description

You start at position (sx, sy) on an infinite 2D grid. Your goal is to reach position (fx, fy) in exactly t seconds.

Each second, you must move to one of the 8 adjacent cells around your current position. These adjacent cells are the ones that share at least one corner with your current cell (including diagonal moves). You can revisit cells multiple times.

Given the starting coordinates (sx, sy), destination coordinates (fx, fy), and a non-negative integer t representing the time limit, determine if it's possible to reach the destination in exactly t seconds.

The function should return true if you can reach (fx, fy) after exactly t seconds, and false otherwise.

Key Points:

• You must move every second (you cannot stay in place)
• You can move in 8 directions (horizontally, vertically, and diagonally)
• You must use exactly t seconds, no more and no less
• The grid is infinite, so there are no boundaries
• You can visit the same cell multiple times during your journey

Intuition

The key insight is to find the minimum number of moves required to reach the destination, then determine if we can use exactly t moves.

Since we can move diagonally, the minimum distance between two points isn't the Manhattan distance, but rather the Chebyshev distance (or chessboard distance). When we can move diagonally, we can cover both x and y distances simultaneously. For example, to go from (0, 0) to (3, 2), we can move diagonally twice (covering 2 units in both x and y), then move once more horizontally. This takes max(3, 2) = 3 moves minimum.

So the minimum moves needed is max(|fx - sx|, |fy - sy|).

Once we know the minimum moves required, we need to consider if we can use exactly t moves:

1. If t equals the minimum moves needed: We can reach the destination exactly.

2. If t is greater than minimum moves: We can reach the destination early and then "waste" the remaining moves. We can do this by moving back and forth between any two adjacent cells. For instance, move right then left repeatedly, or move to any adjacent cell and back.

3. Special case - starting point equals destination: If we're already at the destination (sx == fx and sy == fy), the minimum moves is 0. However, since we MUST move every second, we cannot stay put. If t = 1, it's impossible (we'd have to move away and can't get back in 1 move). For any other t value (0, 2, 3, ...), we can move away and come back, using exactly t moves.

This leads to our solution: check if the minimum required moves max(|fx - sx|, |fy - sy|) is less than or equal to t, with special handling for the case where start equals destination.

Learn more about Math patterns.

Solution Approach

The implementation follows directly from our intuition with a simple case-based approach:

Case 1: Starting point equals destination

When sx == fx and sy == fy, we're already at the destination. Since we must move every second:

• If t = 1: It's impossible. We'd move away but can't return in just 1 move.
• If t = 0 or t ≥ 2: It's possible. We can move to an adjacent cell and come back (takes 2 moves), and repeat this pattern as needed.

This is handled by the condition: return t != 1

Case 2: Starting point differs from destination

We calculate the minimum moves required using the Chebyshev distance:

• dx = abs(sx - fx) - absolute difference in x-coordinates
• dy = abs(sy - fy) - absolute difference in y-coordinates
• Minimum moves = max(dx, dy)

Since we can move diagonally, we can cover the shorter distance while simultaneously covering part of the longer distance. The remaining moves will be along the axis with the larger difference.

Finally, we check if max(dx, dy) <= t:

• If true: We can reach the destination in the minimum required moves, and any extra time can be used to move back and forth between adjacent cells.
• If false: We don't have enough time to reach the destination.

Complete Algorithm:

if sx == fx and sy == fy:
    return t != 1
dx = abs(sx - fx)
dy = abs(sy - fy)
return max(dx, dy) <= t

The solution runs in O(1) time and space complexity, as we only perform constant-time arithmetic operations and comparisons.

Example Walkthrough

Let's walk through a few examples to illustrate the solution approach:

Example 1: Simple diagonal movement

• Start: (sx, sy) = (1, 1), Destination: (fx, fy) = (3, 4), Time: t = 3
• Calculate differences: dx = |3 - 1| = 2, dy = |4 - 1| = 3
• Minimum moves needed: max(2, 3) = 3
• Since 3 ≤ 3, we can reach the destination in exactly 3 seconds
• Path: (1,1) → (2,2) → (3,3) → (3,4)
• Result: true

Example 2: Extra time available

• Start: (sx, sy) = (0, 0), Destination: (fx, fy) = (2, 2), Time: t = 5
• Calculate differences: dx = |2 - 0| = 2, dy = |2 - 0| = 2
• Minimum moves needed: max(2, 2) = 2
• Since 2 ≤ 5, we have 3 extra seconds after reaching the destination
• Path: (0,0) → (1,1) → (2,2) → (2,3) → (2,2) → (2,3) (reach in 2 moves, then oscillate)
• Result: true

Example 3: Not enough time

• Start: (sx, sy) = (1, 2), Destination: (fx, fy) = (7, 9), Time: t = 5
• Calculate differences: dx = |7 - 1| = 6, dy = |9 - 2| = 7
• Minimum moves needed: max(6, 7) = 7
• Since 7 > 5, we don't have enough time to reach the destination
• Result: false

Example 4: Already at destination (special case)

• Start: (sx, sy) = (3, 3), Destination: (fx, fy) = (3, 3), Time: t = 1

• We're already at the destination, but must move every second

• With t = 1, we'd move away but cannot return in just 1 move

• Result: false

• Same scenario with t = 2:

• Path: (3,3) → (3,4) → (3,3) (move away and come back)

• Result: true

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the algorithm performs a fixed number of operations regardless of the input size. It only involves:

• Two equality comparisons (sx == fx and sy == fy)
• One inequality comparison (t != 1)
• Two absolute value calculations (abs(sx - fx) and abs(sy - fy))
• One max() operation between two values
• One comparison (max(dx, dy) <= t)

All these operations take constant time.

The space complexity is O(1) because the algorithm only uses a constant amount of extra space. It stores:

• Two integer variables dx and dy

No additional data structures are created, and the space usage doesn't depend on the input values.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the Special Case When Start Equals Destination

The Problem: Many developers initially write code like this:

def isReachableAtTime(self, sx, sy, fx, fy, t):
    x_distance = abs(sx - fx)
    y_distance = abs(sy - fy)
    min_time_needed = max(x_distance, y_distance)
    return min_time_needed <= t

This looks correct at first glance - if we're already at the destination (distance = 0), and we have any time t ≥ 0, it should return True. However, this fails for the case where sx == fx, sy == fy, and t = 1.

Why It Fails: When we're already at the destination and have exactly 1 second:

• We MUST move (we can't stay in place)
• After moving to any adjacent cell, we've used our 1 second
• We're now not at the destination, making it impossible

The Solution: Always handle the special case explicitly:

if sx == fx and sy == fy:
    return t != 1  # Can't reach in exactly 1 second, but any other time is fine

Pitfall 2: Using Manhattan Distance Instead of Chebyshev Distance

The Problem: Some might incorrectly calculate the minimum distance as:

min_time_needed = abs(sx - fx) + abs(sy - fy)  # Wrong!

Why It Fails: Manhattan distance assumes you can only move horizontally or vertically, not diagonally. For example:

• From (0, 0) to (3, 3)
• Manhattan distance: 3 + 3 = 6 moves
• Actual minimum with diagonal moves: 3 moves (moving diagonally 3 times)

The Solution: Use Chebyshev distance (maximum of the two coordinate differences):

min_time_needed = max(abs(sx - fx), abs(sy - fy))  # Correct!

Pitfall 3: Thinking Extra Moves Are Impossible

The Problem: Some might think that if the minimum distance is 5 and we have 7 seconds, it's impossible because we have "extra" time:

def isReachableAtTime(self, sx, sy, fx, fy, t):
    # Wrong logic: thinking we need EXACTLY the minimum time
    min_time_needed = max(abs(sx - fx), abs(sy - fy))
    return min_time_needed == t  # Wrong!

Why It Fails: We can always use extra time by moving back and forth between adjacent cells. For instance:

• Reach the destination in minimum time
• Move to an adjacent cell
• Move back to the destination
• Repeat as needed to use up remaining time

The Solution: Check if we have AT LEAST the minimum time needed:

return min_time_needed <= t  # We can use extra time for back-and-forth moves