Is Determine if a Cell Is Reachable at a Given Time easy or hard?

The problem is labeled Medium because the trick is recognizing Chebyshev distance and the special edge case. Once the observation is made, the implementation becomes a constant‑time check with only a few arithmetic operations.

Determine if a Cell Is Reachable at a Given Time Python/Java solution

Most implementations compute the Chebyshev distance using simple arithmetic. Python, Java, C++, and JavaScript versions typically calculate dx = abs(sx - fx) and dy = abs(sy - fy), check max(dx, dy) <= t, and handle the edge case where sx == fx, sy == fy, and t == 1.

How to solve Determine if a Cell Is Reachable at a Given Time in O(1)?

Calculate the Chebyshev distance between the start and finish cells: max(|sx - fx|, |sy - fy|). If this minimum distance is greater than t, the destination cannot be reached. If it is less than or equal to t, the destination is reachable except when the start and finish are the same cell and t equals 1, because you must move but cannot return in one step.

What is the best approach for Determine if a Cell Is Reachable at a Given Time?

The optimal approach uses Chebyshev distance. Compute max(|sx - fx|, |sy - fy|) to get the minimum number of moves required when diagonal movement is allowed. If this value is greater than t, reaching the cell is impossible; otherwise it is reachable except for the special case where the start equals the end and t equals 1. This solution runs in O(1) time and O(1) space.

Is Determine if a Cell Is Reachable at a Given Time asked at Google/Amazon/Meta?

Grid movement and distance‑calculation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test recognition of Manhattan or Chebyshev distance and the ability to replace brute‑force graph traversal with a mathematical shortcut.

What data structure is used in Determine if a Cell Is Reachable at a Given Time?

The optimal solution does not require any data structure because it relies on a mathematical distance formula. A brute‑force simulation version may use a queue for Breadth‑First Search along with a visited set to track explored grid cells.

What is the time complexity of Determine if a Cell Is Reachable at a Given Time?

The optimal mathematical solution runs in O(1) time and O(1) space because it only computes absolute differences and a maximum operation. A simulation approach using BFS explores reachable grid cells and can take O(t²) time and space since the search area grows with the number of steps.

Description Hints 3 Solution Video 26:51

2849. Determine if a Cell Is Reachable at a Given Time

Q: How to solve Determine if a Cell Is Reachable at a Given Time in O(1)?

Calculate the Chebyshev distance between the start and finish cells: max(|sx - fx|, |sy - fy|). If this minimum distance is greater than t, the destination cannot be reached. If it is less than or equal to t, the destination is reachable except when the start and finish are the same cell and t equals 1, because you must move but cannot return in one step.

Q: What is the best approach for Determine if a Cell Is Reachable at a Given Time?

The optimal approach uses Chebyshev distance. Compute max(|sx - fx|, |sy - fy|) to get the minimum number of moves required when diagonal movement is allowed. If this value is greater than t, reaching the cell is impossible; otherwise it is reachable except for the special case where the start equals the end and t equals 1. This solution runs in O(1) time and O(1) space.

Q: Is Determine if a Cell Is Reachable at a Given Time asked at Google/Amazon/Meta?

Grid movement and distance‑calculation problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test recognition of Manhattan or Chebyshev distance and the ability to replace brute‑force graph traversal with a mathematical shortcut.

Q: What data structure is used in Determine if a Cell Is Reachable at a Given Time?

The optimal solution does not require any data structure because it relies on a mathematical distance formula. A brute‑force simulation version may use a queue for Breadth‑First Search along with a visited set to track explored grid cells.

Q: What is the time complexity of Determine if a Cell Is Reachable at a Given Time?

The optimal mathematical solution runs in O(1) time and O(1) space because it only computes absolute differences and a maximum operation. A simulation approach using BFS explores reachable grid cells and can take O(t²) time and space since the search area grows with the number of steps.

Medium37.2% acceptance2 companies

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⁹

Asked at 2 companies

GitHub

Google

Topics

Math

Hints open one at a time

Hint 1

Minimum time to reach the cell should be less than or equal to given time.

Hint 2

The answer is true if t is greater or equal than the Chebyshev distance from (sx, sy) to (fx, fy). However, there is one more edge case to be considered.

Hint 3

The answer is false If sx == fx and sy == fy

26:51

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution