Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Method 1 – Chebyshev Distance (King’s Move)

Intuition

On an infinite grid, you can move to any of the 8 adjacent cells in one second (like a king in chess). The minimum number of steps to reach (fx, fy) from (sx, sy) is the Chebyshev distance: max(|sx - fx|, |sy - fy|). You can always reach the target in exactly t steps if t is at least this distance, except for the special case where you start and end at the same cell and t == 1 (since you must move at least once).

Approach

  1. Compute the Chebyshev distance: d = max(|sx - fx|, |sy - fy|).
  2. If starting and ending at the same cell, you can only stay put if t != 1 (since you must move each second).
  3. Otherwise, return true if t >= d.

Code

1
2
3
4
5
6
7
8

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

func isReachableAtTime(sx, sy, fx, fy, t int) bool {
    if sx == fx && sy == fy {
        return t != 1
    }
    d := abs(sx-fx)
    if abs(sy-fy) > d { d = abs(sy-fy) }
    return d <= t
}
func abs(x int) int { if x < 0 { return -x }; return x }
1
2
3
4
5
6
7

class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy) return t != 1;
        int d = Math.max(Math.abs(sx - fx), Math.abs(sy - fy));
        return d <= t;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun isReachableAtTime(sx: Int, sy: Int, fx: Int, fy: Int, t: Int): Boolean {
        if (sx == fx && sy == fy) return t != 1
        val d = maxOf(kotlin.math.abs(sx - fx), kotlin.math.abs(sy - fy))
        return d <= t
    }
}
1
2
3
4
5
6

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
        d = max(abs(sx - fx), abs(sy - fy))
        return d <= t
1
2
3
4
5
6
7

impl Solution {
    pub fn is_reachable_at_time(sx: i32, sy: i32, fx: i32, fy: i32, t: i32) -> bool {
        if sx == fx && sy == fy { return t != 1; }
        let d = (sx - fx).abs().max((sy - fy).abs());
        d <= t
    }
}
1
2
3
4
5
6
7

class Solution {
    isReachableAtTime(sx: number, sy: number, fx: number, fy: number, t: number): boolean {
        if (sx === fx && sy === fy) return t !== 1;
        const d = Math.max(Math.abs(sx - fx), Math.abs(sy - fy));
        return d <= t;
    }
}

Complexity

  • ⏰ Time complexity: O(1), all operations are constant time.
  • 🧺 Space complexity: O(1).