2849. Determine if a Cell Is Reachable at a Given Time
Problem Description
In this problem, you are placed on an infinite 2D grid at coordinates (sx, sy)
. Your task is to determine whether you can reach a specific cell (fx, fy)
in exactly t
seconds. The movement is restricted to each second and you must move to any of the 8 cells adjacent to your current cell. Those cells can be directly to the north, northeast, east, southeast, south, southwest, west, or northwest of the cell you're currently in. You can revisit cells multiple times.
Intuition
The intuitive approach to this problem is to consider the minimum number of moves required to go from (sx, sy)
to (fx, fy)
. The number of moves is simply the maximum of the horizontal and vertical distances between the start and end points (dx
and dy
). Since we can move to any of the 8 adjacent cells each second, we can increment either or both the x and y positions by 1 each second, heading directly toward the destination in a diagonal line until we line up horizontally or vertically, then moving straight towards the destination.
Now, if these minimum required moves exceed t
, it's impossible to reach the destination in time. However, if t
is exactly enough for these moves or more, it becomes possible. There's a catch, though: we cannot reach the exact cell in one move since our first move will always place us in one of the 8 adjacent cells around (sx, sy)
and never exactly at (sx, sy)
again, so we must check if t
is not equal to 1 when the start and end points are the same. Taking all this into account, the solution checks if the maximum of dx
and dy
is less than or equal to t
and handles the special case where the start and end points are the same.
Learn more about Math patterns.
Solution Approach
The implementation of the provided solution approach is straightforward and does not involve complex algorithms or data structures. It relies on absolute differences and comparison operations. Here's a breakdown of the steps followed:
-
The code begins by checking if the starting cell
(sx, sy)
is the same as the final cell(fx, fy)
. If they are the same andt
is not 1, it returnsTrue
as you can simply stay in place fort
seconds. Ift
is 1, you cannot stay in the same cell since you must move every second, hence it returnsFalse
. -
If the starting cell and the final cell are different, the Manhattan distance is not directly used here. Instead, the code calculates the horizontal distance
dx
by finding the absolute difference betweensx
andfx
and the vertical distancedy
by finding the absolute difference betweensy
andfy
. -
Then, since you could move in a diagonal direction (in which both the
x
andy
coordinates change), the code finds the maximum ofdx
anddy
. This is because moving diagonally will reduce bothdx
anddy
until you align horizontally or vertically with the target cell, at which point you will only need to move in one direction to reach the cell. -
To reach the destination in exactly
t
seconds, the maximum required steps (eitherdx
ordy
) must be less than or equal tot
. This ensures that there is the possibility of exactly matching the distance in the given time or having extra time to move around but still end up on the target cell by thet
-th second.
The provided code snippet puts this approach into practice with an if
condition and a couple of absolute value calculations. No additional patterns, algorithms, or data structures are needed since the problem is concerned only with calculating distances and not with the specific path taken.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach described.
Suppose we start at sx = 2, sy = 3
and want to reach fx = 5, fy = 7
in exactly t = 5
seconds.
-
We check if the starting cell
(sx, sy)
is the same as the final cell(fx, fy)
. Here, they are not the same, so we will need to move. -
Next, we calculate the absolute differences for both the horizontal and vertical distances. The horizontal distance
dx
is|5 - 2| = 3
, and the vertical distancedy
is|7 - 3| = 4
. -
The maximum of
dx
anddy
is used to find the minimum number of seconds required to reach the target cell. Betweendx=3
anddy=4
, the maximum is4
. This is the minimum number of seconds we need to reach the target cell, moving diagonally whenever possible. -
We check if we can reach the destination in exactly
t
seconds. Sincet = 5
, which is greater than the maximum ofdx
anddy
, it is possible to reachfx, fy
in exactlyt
seconds. We have one extra second that we can use to move to an adjacent cell and come back, or simply move in a non-optimal path that ensures we end up on(fx, fy)
after 5 seconds.
Based on these steps, the solution would return True
, indicating that yes, we can indeed reach cell (5, 7)
from (2, 3)
in exactly 5
seconds.
Solution Implementation
1class Solution:
2 def isReachableAtTime(self, start_x: int, start_y: int, finish_x: int, finish_y: int, time: int) -> bool:
3 # If the start and finish coordinates are the same
4 if start_x == finish_x and start_y == finish_y:
5 # If the time is not equal to 1 then it is reachable at the given time
6 return time != 1
7
8 # Calculate the absolute differences in x and y coordinates
9 delta_x = abs(start_x - finish_x)
10 delta_y = abs(start_y - finish_y)
11
12 # Check whether the larger of the x and y differences is within the available time
13 # This determines if the target can be reached at the given time
14 return max(delta_x, delta_y) <= time
15
1class Solution {
2
3 /**
4 * Determines if it's possible to reach from the starting point to the final
5 * point in a given time t.
6 *
7 * @param startX The starting x-coordinate.
8 * @param startY The starting y-coordinate.
9 * @param finalX The final x-coordinate.
10 * @param finalY The final y-coordinate.
11 * @param time The time constraint within which the point must be reached.
12 * @return A boolean indicating whether it is possible to reach the final point in time or not.
13 */
14 public boolean isReachableAtTime(int startX, int startY, int finalX, int finalY, int time) {
15 // Check if the starting and final points are the same and ensure time is not 1
16 if (startX == finalX && startY == finalY) {
17 return time != 1;
18 }
19
20 // Calculate the distance from the starting point to the final point for both x and y coordinates
21 int distanceX = Math.abs(startX - finalX);
22 int distanceY = Math.abs(startY - finalY);
23
24 // Return true if the maximum distance on either the x-axis or y-axis
25 // is less than or equal to allowed time
26 return Math.max(distanceX, distanceY) <= time;
27 }
28}
29
1class Solution {
2public:
3 // Check if it's possible to reach from (startX, startY) to (finishX, finishY) in 't' time steps.
4 bool isReachableAtTime(int startX, int startY, int finishX, int finishY, int time) {
5 // If starting and finishing positions are the same, we can't reach in exactly one step.
6 if (startX == finishX && startY == finishY) {
7 return time != 1;
8 }
9
10 // Calculate the distance needed to travel in x and y direction.
11 int deltaX = abs(finishX - startX);
12 int deltaY = abs(finishY - startY);
13
14 // Check if the maximum number of steps required in either x or y direction is less than or equal to the available time steps.
15 return max(deltaX, deltaY) <= time;
16 }
17};
18
1// Function to determine if it is possible to reach the final destination (fx, fy)
2// from the starting position (sx, sy) within the time 't'.
3function isReachableAtTime(startX: number, startY: number, finalX: number, finalY: number, time: number): boolean {
4 // Check if the start and final positions are the same
5 if (startX === finalX && startY === finalY) {
6 // If positions are the same and time is not 1, we can reach the destination
7 return time !== 1;
8 }
9
10 // Calculate the absolute differences in x and y coordinates to get the distance
11 const distanceX = Math.abs(startX - finalX);
12 const distanceY = Math.abs(startY - finalY);
13
14 // Return true if the maximum of the x or y distance is less than or equal to the available time
15 return Math.max(distanceX, distanceY) <= time;
16}
17
Time and Space Complexity
The time complexity of the code is O(1)
, as all operations performed in the isReachableAtTime
function are constant time operations. There are no loops or recursive calls that depend on the size of the input. The function performs arithmetic operations and comparisons, which take constant time regardless of the values of sx
, sy
, fx
, fy
, and t
.
The space complexity of the code is also O(1)
since the amount of memory used does not scale with the input size. The function only uses a fixed amount of additional memory for variables dx
and dy
, which does not change with the size of the input values.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.