LeetCode 2849 - Determine if a Cell Is Reachable at a Given Time

This problem asks whether it is possible to reach a specific target cell (fx, fy) from a starting cell (sx, sy) in an infinite 2D grid in exactly t seconds. Each second, movement must occur to one of the eight adjacent cells, including diagonals.

leetcodemediummath

LeetCode Problem 2849

Difficulty: 🟡 Medium
Topics: Math

Solution

Problem Understanding

This problem asks whether it is possible to reach a specific target cell (fx, fy) from a starting cell (sx, sy) in an infinite 2D grid in exactly t seconds. Each second, movement must occur to one of the eight adjacent cells, including diagonals. The grid is effectively unbounded, so we do not have to worry about borders.

The inputs are integers representing coordinates on the grid and a non-negative integer t representing the number of seconds available. The expected output is a boolean: true if it is possible to reach (fx, fy) in exactly t steps, and false otherwise.

Key points to notice are that moving diagonally allows us to reduce both x and y distances simultaneously, and revisiting cells is allowed. The constraints are large, up to 10^9, which rules out any brute-force simulation of every possible path. Edge cases to consider include sx == fx and/or sy == fy (starting already at the target), t == 0, and situations where t is smaller than the minimum required moves.

The problem guarantees valid positive integer coordinates and a non-negative t, ensuring that negative or zero-length coordinates are not an issue.

Approaches

Brute Force

A brute-force approach would involve performing a breadth-first search (BFS) or depth-first search (DFS) from (sx, sy), enumerating all possible sequences of moves for t seconds, and checking if (fx, fy) is reached at the final step. While correct, this is infeasible because the number of positions grows exponentially with t. Given that t can be up to 10^9, this approach would take an astronomical amount of time and memory.

Optimal Approach

The key insight is that each move allows you to change your coordinates by at most 1 in x and/or y, so the minimum number of seconds required to reach (fx, fy) is determined by the Chebyshev distance:

min_steps = max(abs(fx - sx), abs(fy - sy))

Since we can move diagonally, this formula accounts for simultaneous x and y movement. After reaching the target in min_steps, any remaining time t - min_steps can be spent moving back and forth (since revisiting cells is allowed), but this is only possible if the remaining time is non-negative. Therefore, the condition to return true is:

t >= min_steps

This observation gives a constant-time solution without simulation.

Approach Time Complexity Space Complexity Notes
Brute Force O(8^t) O(t^2) Explore all paths up to t steps; infeasible for large t
Optimal O(1) O(1) Compute Chebyshev distance and compare with t

Algorithm Walkthrough

  1. Compute the horizontal and vertical differences between the start and target:
dx = abs(fx - sx)
dy = abs(fy - sy)
  1. Determine the minimum number of steps required using Chebyshev distance:
min_steps = max(dx, dy)

This is because diagonal moves reduce both dx and dy by 1 simultaneously.

  1. Compare min_steps with the available time t. If t is less than min_steps, it is impossible to reach the target in exactly t seconds, so return false.
  2. If t is greater than or equal to min_steps, return true, because any extra time can be spent revisiting cells to "waste" steps until exactly t seconds have passed.

Why it works: Chebyshev distance correctly models the fastest route considering diagonal movement. Because revisiting cells is allowed, any extra time can be used without constraint. This guarantees correctness for all valid input values.

Python Solution

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        dx = abs(fx - sx)
        dy = abs(fy - sy)
        min_steps = max(dx, dy)
        return t >= min_steps

The implementation first computes the absolute differences between the start and target coordinates. It then computes the Chebyshev distance to find the minimum steps required. Finally, it checks if the given time t is sufficient to reach the target. Since revisiting cells is allowed, no further checks are necessary.

Go Solution

func isReachableAtTime(sx int, sy int, fx int, fy int, t int) bool {
    dx := fx - sx
    if dx < 0 {
        dx = -dx
    }
    dy := fy - sy
    if dy < 0 {
        dy = -dy
    }
    minSteps := dx
    if dy > dx {
        minSteps = dy
    }
    return t >= minSteps
}

The Go implementation mirrors the Python solution, using conditional statements instead of abs from the standard library. It calculates the minimum required steps and checks if the time is sufficient.

Worked Examples

Example 1

Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6

dx = abs(7 - 2) = 5
dy = abs(7 - 4) = 3
min_steps = max(5, 3) = 5
t = 6
t >= min_steps -> 6 >= 5 -> true

Output: true

Example 2

Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3

dx = abs(7 - 3) = 4
dy = abs(3 - 1) = 2
min_steps = max(4, 2) = 4
t = 3
t >= min_steps -> 3 >= 4 -> false

Output: false

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only arithmetic operations are performed; independent of input size
Space O(1) Only a few variables are used; no data structures or recursion

The solution is extremely efficient because it avoids any iteration over the grid or path simulation. It relies entirely on the Chebyshev distance property.

Test Cases

# Provided examples
assert Solution().isReachableAtTime(2, 4, 7, 7, 6) == True  # diagonal movement possible
assert Solution().isReachableAtTime(3, 1, 7, 3, 3) == False # not enough time

# Edge cases
assert Solution().isReachableAtTime(1, 1, 1, 1, 0) == True  # starting at target, zero time
assert Solution().isReachableAtTime(1, 1, 1, 1, 5) == True  # starting at target, extra time
assert Solution().isReachableAtTime(1, 1, 2, 2, 1) == True  # one diagonal step
assert Solution().isReachableAtTime(1, 1, 2, 2, 0) == False # insufficient time
assert Solution().isReachableAtTime(1, 1, 1000000000, 1000000000, 1000000000) == True  # large input
assert Solution().isReachableAtTime(1, 1, 1000000000, 1000000000, 999999999) == False # large input, insufficient time
Test Why
(2,4)->(7,7), t=6 Normal diagonal path with extra time
(3,1)->(7,3), t=3 Insufficient time for minimum path
(1,1)->(1,1), t=0 Starting at target, zero time
(1,1)->(1,1), t=5 Extra time allowed at target
(1,1)->(2,2), t=1 Minimum diagonal step
(1,1)->(2,2), t=0 Not enough time for move
Large coordinates reachable Tests performance and correctness for large inputs
Large coordinates unreachable Tests failure for large inputs

Edge Cases

Starting at the target: If sx == fx and sy == fy, the minimum steps are zero. The function correctly handles t = 0 (must stay put) and t > 0 (extra steps can be wasted revisiting cells).

Insufficient time: If t < min_steps, reaching the target is impossible. This is correctly captured by the comparison t >= min_steps.

Large coordinates: The function uses only arithmetic operations on integers. Even with maximum inputs up to 10^9, there is no risk of integer overflow in Python. In Go, all arithmetic stays within 32 or 64-bit limits since the difference and max remain within the range of int.

Extra time: Any extra time beyond min_steps can be spent moving back and forth. This guarantees the "exactly t seconds" requirement without simulating paths. The algorithm inherently accounts for this