#2849

Medium

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Determine if a Cell Is Reachable at a Given Time

The problem asks if a target cell can be reached from a starting position within a given time on a 2D grid.

Problem Statement

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 one of the adjacent cells. You need to determine if it is possible to reach the target cell (fx, fy) after exactly t seconds.

Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise. Consider the minimum time needed to reach the target from the starting cell and check if it matches the given time t.

Examples

Example 1

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

Output: true

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

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 <= 109
0 <= t <= 109

Solution Approach

Calculate Minimum Time to Reach Target

The key to solving this problem is calculating the minimum time required to reach the target cell. This can be done by computing the Manhattan distance between the starting point (sx, sy) and the target point (fx, fy). The formula for Manhattan distance is |sx - fx| + |sy - fy|.

Compare Minimum Time with Given Time

Once the minimum time is calculated, simply check if it is less than or equal to the given time t. If it is, check if the difference between t and the minimum time is even. If so, the target cell can be reached exactly at time t; otherwise, it cannot.

Return True or False

Return true if the target cell can be reached exactly at time t, otherwise return false. The key check is whether the time difference between the minimum time and t is even, which allows exact movement to the target cell.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

The time complexity is O(1) as it involves basic arithmetic operations. The space complexity is O(1) because only a few variables are used for calculation.

What Interviewers Usually Probe

The candidate's ability to recognize and use the Manhattan distance in a 2D grid.
Checking the evenness of the difference between minimum time and t to ensure exact movement.
Efficiency in arriving at the correct result with minimal operations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check if the difference between minimum time and t is even, which would lead to incorrect results.
Misunderstanding that movement can be in any direction, requiring the use of Manhattan distance rather than Euclidean distance.
Confusing the minimum time to reach the target with the exact time condition t.

Follow-up variants

Consider a problem where the time t is replaced by a time range and check if the target can be reached within that range.
Expand the grid to a 3D space, requiring adjustment to the movement calculations.
Introduce obstacles or constraints on movement that change the time calculation and test adaptability.

FAQ

How do I calculate the minimum time to reach the target cell?

You calculate the minimum time using the Manhattan distance formula: |sx - fx| + |sy - fy|.

What do I do if the minimum time is not equal to the given time t?

Check if the difference between the minimum time and t is even. If it is, return true; otherwise, return false.

What if the time t is smaller than the minimum time?

If t is smaller than the minimum time, it's impossible to reach the target in the given time, so return false.

Can the target cell be unreachable even if the minimum time is less than t?

Yes, if the difference between t and the minimum time is not even, you cannot reach the target at exactly time t.

What is the main algorithmic pattern in this problem?

The main algorithmic pattern is based on the math-driven solution strategy using the Manhattan distance to determine the minimum time.

terminal

Solution

Solution 1: Case Discussion

If the starting point and the destination are the same, then we can only reach the destination within the given time if $t \neq 1$.

1

2

3

4

5

6

7

class Solution:
    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

Continue Practicing

#2851 string transformation #2844 minimum operations to make a special number #2843 count symmetric integers