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

MediumMath

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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 and t is not 1, it returns True as you can simply stay in place for t seconds. If t is 1, you cannot stay in the same cell since you must move every second, hence it returns False.
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 between sx and fx and the vertical distance dy by finding the absolute difference between sy and fy.
Then, since you could move in a diagonal direction (in which both the x and y coordinates change), the code finds the maximum of dx and dy. This is because moving diagonally will reduce both dx and dy 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 (either dx or dy) must be less than or equal to t. 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 the t-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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Example 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 distance dy is |7 - 3| = 4.
The maximum of dx and dy is used to find the minimum number of seconds required to reach the target cell. Between dx=3 and dy=4, the maximum is 4. 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. Since t = 5, which is greater than the maximum of dx and dy, it is possible to reach fx, fy in exactly t 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

Not Sure What to Study? Take the 2-min Quiz：

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

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

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings