Determine if a Cell Is Reachable at a Given Time solution and explanation
Google
9 more videos on this problem
Determine if a Cell Is Reachable at a Given Time | Intuition | Math | Leetcode - 2849codestorywithMIK · 26:51 · 3K views
🔴 2849. Determine if a Cell Is Reachable at a Given Time II Math II Easy & ConciseAryan Mittal · 11:00 · 2K views
2849. Determine if a Cell Is Reachable at a Given Time | Greedy | O(1) timeAryan Mittal · 15:15 · 1K views
2849. Determine if a Cell Is Reachable at a Given Time || 2D MathsAyush Rao · 10:52 · 557 views
2849. Determine if a Cell Is Reachable at a Given Time (Leetcode Medium)Programming Live with Larry · 8:14 · 512 views
Daily Leetcode #1317: Nov 08, 2023 - 2849. Determine if a Cell Is Reachable at a Given TimeProgramming Live with Larry · 6:47 · 284 views
😍2849. Determine if a Cell Is Reachable at a Given TimeCP Geeks · 8:02 · 241 views
2849. Determine if a Cell Is Reachable at a Given Time (with a FAANG engineer)TechTalk · 8:46 · 180 views
✅ Determine if a Cell Is Reachable at a Given Time ✅ Easiest Possible Interview Solution - ExplainedLeet Logics · 8:51 · 160 views
2849. Determine if a Cell Is Reachable at a Given TimeCodeCoderCoding · 1:08 · 103 views
The 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.
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 <= 1090 <= t <= 109
Approach overview
Problem Overview: You start at cell (sx, sy) on an infinite grid and want to reach (fx, fy) exactly at time t. In one second you may move to any of the 8 neighboring cells (horizontal, vertical, or diagonal). The task is to determine whether the destination can be reached in exactly t moves.
Approach 1: Minimum Steps with Parity Check (O(1) time, O(1) space)
The key observation is that diagonal movement allows you to reduce both row and column distance at the same time. The minimum number of moves needed is the Chebyshev distance: max(|sx - fx|, |sy - fy|). If this minimum distance is greater than t, reaching the target is impossible. If the distance is less than or equal to t, you can usually spend extra moves by wandering around nearby cells.
There is one edge case: when the start and end cells are the same and t = 1. Any move must change the position, so returning to the same cell in exactly one step is impossible. For all other cases where t is at least the minimum distance, the destination is reachable. This constant‑time observation makes the problem a pure math reasoning exercise rather than a full search.
Approach 2: Simulation with BFS Algorithm (O(t²) time, O(t²) space)
A straightforward approach treats the grid as a graph where each cell connects to its eight neighbors. Starting from (sx, sy), perform a Breadth‑First Search (BFS) and expand all reachable cells level by level until time t. If the destination appears at exactly level t, return true.
Because the grid is infinite, BFS must be limited to cells that can possibly be reached within t moves, effectively a square region around the start. This leads to roughly O(t²) states in the worst case. While this approach models the movement rules directly and is easy to reason about, it is far slower than the mathematical observation.
Recommended for interviews: Interviewers expect the constant‑time math solution using Chebyshev distance. It shows you recognize the movement pattern of 8-direction grids and avoid unnecessary graph traversal. Discussing the BFS simulation first can demonstrate baseline reasoning, but the O(1) approach proves stronger algorithmic insight.
Approach 1: Approach 1: Minimum Steps with Parity Check
This approach leverages the concept of "Manhattan distance" coupled with the "parity check" to determine if the cell can be reached in exactly t steps.
The minimum number of steps required to reach from (sx, sy) to (fx, fy) in a grid is the maximum of the horizontal and vertical distances between these points, known as Chebyshev distance. If this minimal distance is greater than t, the function should return false instantly.
Moreover, if the difference between t and this minimum distance is even, the extra steps required can effectively be taken by oscillating on the grid or taking additional allowable steps. If not, reaching in t steps becomes impossible.
def is_cell_reachable(sx, sy, fx, fy, t):
min_steps = max(abs(fx - sx), abs(fy - sy))
return min_steps <= t and (t - min_steps) % 2 == 0public class Solution {
public boolean isCellReachable(int sx, int sy, int fx, int fy, int t) {
int min_steps = Math.max(Math.abs(fx - sx), Math.abs(fy - sy));
return min_steps <= t && (t - min_steps) % 2 == 0;
}
}#include <iostream>
#include <cmath>
bool isCellReachable(int sx, int sy, int fx, int fy, int t) {
int min_steps = std::max(std::abs(fx - sx), std::abs(fy - sy));
return (min_steps <= t && (t - min_steps) % 2 == 0);
}function isCellReachable(sx, sy, fx, fy, t) {
const min_steps = Math.max(Math.abs(fx - sx), Math.abs(fy - sy));
return min_steps <= t && (t - min_steps) % 2 === 0;
}#include <stdbool.h>
#include <math.h>
bool isCellReachable(int sx, int sy, int fx, int fy, int t) {
int min_steps = fmax(abs(fx - sx), abs(fy - sy));
return (min_steps <= t && (t - min_steps) % 2 == 0);
}public class Solution {
public bool IsCellReachable(int sx, int sy, int fx, int fy, int t) {
int min_steps = Math.Max(Math.Abs(fx - sx), Math.Abs(fy - sy));
return min_steps <= t && (t - min_steps) % 2 == 0;
}
}The Python function computes the required minimum steps and parity check using simple built-in functions and returns True or False based on whether it can reach in exactly t steps.
Time Complexity: O(1)
Space Complexity: O(1)
Approach 2: Approach 2: Simulation with BFS Algorithm
This approach models the grid and implements a Breadth-First Search (BFS) to simulate traversing from the starting point to check if reaching precisely at t seconds is possible.
Instead of directly computing the distance, this method carries out a brute-force simulation of the movement, exploring all potential paths using a FIFO queue structure inherent to BFS algorithms. The goal is to maintain a count of steps and analyze pathways that may uniquely cover the grid in t steps.
from collections import deque
def is_cell_reachable(sx, sy, fx, fy, t):
queue = deque([(sx, sy, 0)])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
while queue:
x, y, steps = queue.popleft()
if x == fx and y == fy and steps == t:
return True
if steps >= t:
continue
for dx, dy in directions:
queue.append((x + dx, y + dy, steps + 1))
return Falseimport java.util.*;
public boolean isCellReachable(int sx, int sy, int fx, int fy, int t) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sx, sy, 0});
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
while (!queue.isEmpty()) {
int[] node = queue.poll();
int x = node[0], y = node[1], steps = node[2];
if (x == fx && y == fy && steps == t)
return true;
if (steps >= t)
continue;
for (int[] dir : dirs) {
queue.offer(new int[]{x + dir[0], y + dir[1], steps + 1});
}
}
return false;
}#include <queue>
#include <cmath>
#include <utility>
using namespace std;
bool isCellReachable(int sx, int sy, int fx, int fy, int t) {
queue<pair<pair<int, int>, int>> q;
q.push({{sx, sy}, 0});
int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
while (!q.empty()) {
auto [point, steps] = q.front(); q.pop();
if (point.first == fx && point.second == fy && steps == t) return true;
if (steps >= t) continue;
for (auto d : dir) {
int nx = point.first + d[0], ny = point.second + d[1];
q.push({{nx, ny}, steps + 1});
}
}
return false;
}function isCellReachable(sx, sy, fx, fy, t) {
const queue = [[sx, sy, 0]];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];
while (queue.length > 0) {
const [x, y, steps] = queue.shift();
if (x === fx && y === fy && steps === t) {
return true;
}
if (steps >= t) {
continue;
}
for (const [dx, dy] of directions) {
queue.push([x + dx, y + dy, steps + 1]);
}
}
return false;
}#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
bool bfs(int sx, int sy, int fx, int fy, int t) {
// Assume this is initialized with a queue and relevant BFS logic.
// Left incomplete for basic simulation purposes and brevity.
return false;
}
bool isCellReachable(int sx, int sy, int fx, int fy, int t) {
return bfs(sx, sy, fx, fy, t);
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsCellReachable(int sx, int sy, int fx, int fy, int t) {
Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
queue.Enqueue((sx, sy, 0));
int[][] directions = new int[][]
{
new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1},
new int[] {-1, -1}, new int[] {-1, 1}, new int[] {1, -1}, new int[] {1, 1}
};
while (queue.Count > 0) {
var (x, y, steps) = queue.Dequeue();
if (x == fx && y == fy && steps == t)
return true;
if (steps >= t)
continue;
foreach (var dir in directions) {
queue.Enqueue((x + dir[0], y + dir[1], steps + 1));
}
}
return false;
}
}This Python solution relies upon a deque for queue simulation, conforming to the BFS iterative processes while efficiently managing data related to path exploration.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 3: 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.
Otherwise, we can calculate the difference in the x and y coordinates between the starting point and the destination, and then take the maximum value. If the maximum value is less than or equal to the given time, then we can reach the destination within the given time.
The time complexity is O(1), and the space complexity is O(1).
function isReachableAtTime(sx: number, sy: number, fx: number, fy: number, t: number): boolean {
if (sx === fx && sy === fy) {
return t !== 1;
}
const dx = Math.abs(sx - fx);
const dy = Math.abs(sy - fy);
return Math.max(dx, dy) <= t;
}func isReachableAtTime(sx int, sy int, fx int, fy int, t int) bool {
if sx == fx && sy == fy {
return t != 1
}
dx := abs(sx - fx)
dy := abs(sy - fy)
return max(dx, dy) <= t
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Minimum Steps with Parity Check | Time Complexity: O(1) Space Complexity: O(1) |
| Approach 2: Simulation with BFS Algorithm | Time Complexity: O(n^2) Space Complexity: O(n^2) |
| Case Discussion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Minimum Steps with Parity Check (Math) | O(1) | O(1) | Best approach. Uses Chebyshev distance to compute the minimum moves directly. |
| Simulation with BFS | O(t²) | O(t²) | Useful for understanding grid movement or when deriving the mathematical shortcut. |
Frequently asked questions
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.