Jobs

Interviews

Discussions

Determine if a Cell Is Reachable at a Given Time #3 Most Asked

Medium

GitHub

1 view

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⁹

Try coding it in LeetCode

Determine if a Cell Is Reachable at a Given Time #3 Most Asked

Medium

GitHub

1 view

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⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the starting and target cells be the same?
Can the time 't' be zero or negative?
Are the x and y coordinates of the start and end cells integers?
What are the constraints on the magnitude of the x and y coordinates (e.g., maximum or minimum values)?
If it's impossible to reach the target cell within the given time 't', what should I return (e.g., false, 0, or throw an exception)?

Brute Force Solution

Approach

The brute force approach explores every possible path to see if we can reach the destination within the given time. We systematically try moving in all directions at each step, checking if any of those paths lead us to the goal in the correct amount of time.

Here's how the algorithm would work step-by-step:

Start at the starting location.
Imagine you can move up, down, left, or right from your current location.
Consider all possible single moves you can make from the starting location.
For each of those new locations, again consider all possible moves you can make.
Keep repeating this process, keeping track of how long it takes to get to each new location.
If you ever reach the destination, check if the time taken is exactly the time allowed.
If the time is exactly the allowed time, then the destination is reachable.
If you've explored all possible moves for all possible locations within the time limit, and you haven't found a path that leads to the destination in the correct amount of time, then the destination is not reachable.

Code Implementation

def is_reachable_at_time_brute_force(
    start_row,
    start_column,
    finish_row,
    finish_column,
    allowed_time
):
    # Special case: if start and finish are same
    if start_row == finish_row and start_column == finish_column:
        return allowed_time != 0

    queue = [(start_row, start_column, 0)]

    while queue:
        current_row, current_column, current_time = queue.pop(0)

        # Destination check: if destination and time align return True
        if current_row == finish_row and current_column == finish_column:
            if current_time == allowed_time:
                return True
            else:
                continue

        # Time check: Prune paths exceeding allowed_time
        if current_time >= allowed_time:
            continue

        # Explore all 4 directions
        possible_moves = [
            (current_row + 1, current_column),
            (current_row - 1, current_column),
            (current_row, current_column + 1),
            (current_row, current_column - 1),
        ]

        for next_row, next_column in possible_moves:
            queue.append((next_row, next_column, current_time + 1))

    return False

Big(O) Analysis

Time Complexity

O(4^time) – The brute force approach explores all possible paths within the given time. At each cell, we can move in up to 4 directions. Therefore, the number of possible paths grows exponentially with the allowed time. In the worst case, we explore all possible paths up to the given time limit, leading to a branching factor of 4 for each time unit. Thus, the time complexity is O(4^time), where time is the input time.

Space Complexity

O(time) – The brute force approach, as described, explores all possible paths within the given time limit. This exploration implicitly uses a queue or a call stack (if implemented recursively) to keep track of the locations to visit. In the worst-case scenario, the algorithm might need to explore a large portion of the grid or all possible paths up to the given 'time'. Therefore, the space required to store the locations to visit (either in the queue or call stack) could grow proportionally with the 'time' parameter, since it determines how many moves/locations will be generated and stored. The memory footprint is predominantly impacted by the number of location coordinates and time steps that need to be stored, resulting in O(time) space complexity.

Optimal Solution

Approach

The problem boils down to figuring out the shortest time needed to reach the destination and comparing it with the given time. We need to consider if a straight path or diagonal path is most efficient, and also handle edge cases where the starting point is the destination.

Here's how the algorithm would work step-by-step:

First, find the difference in row and column values between the starting cell and the target cell. These differences tell you how far apart the cells are.
The most efficient way to move is using diagonal steps because they change both the row and column at once.
Find the largest of the row difference and column difference. This value represents the minimum time required to reach the destination because diagonal movements covers both axis at the same time.
If the starting and ending points are the same, the minimum time is considered as two if the allocated time is one, and the answer is true if the allocated time is zero.
Check if the given time is less than the minimum time we calculated. If it is, the target is unreachable.
If the given time is greater or equal to the minimum time, then there's one more check needed.
Subtract the minimum time from the given time. If the remaining time is an even number or zero, the target is reachable. This is because any extra time can be spent by moving back and forth, which consumes 2 units of time per cell.
If the remaining time after subtraction is odd and we can't return to a previous cell for more even subtractions, the target is unreachable.

Code Implementation

def is_reachable_at_time(start_row, start_column, 
    target_row, target_column, given_time):

    row_difference = abs(target_row - start_row)
    column_difference = abs(target_column - start_column)

    #The minimum time required is the max of row and column difference.
    minimum_time_required = max(row_difference, column_difference)

    if start_row == target_row and start_column == target_column:
        # Special case: starting and ending at the same point.
        if given_time == 1:
            return False
        return True

    if given_time < minimum_time_required:
        return False

    remaining_time = given_time - minimum_time_required

    # If remaining time is even, we can always reach the destination.
    if remaining_time % 2 == 0:
        return True
    else:
        #When time is odd, only reachable if min_time > 1.
        if minimum_time_required > 1:
            return True
        else:
            return False

Big(O) Analysis

Time Complexity

O(1) – The solution involves a fixed number of arithmetic operations: calculating the absolute differences between start and target coordinates, finding the maximum of these differences, and performing subtractions and comparisons. These operations take constant time regardless of the input values. There are no loops or recursion that depend on the input size. Thus, the time complexity is O(1).

Space Complexity

O(1) – The provided plain English explanation describes an algorithm that primarily involves calculating differences and comparing values. It only uses a few integer variables to store row and column differences, and the minimum time. Since the number of variables does not depend on the input cell coordinates, the algorithm uses constant extra space. No auxiliary data structures like arrays, lists, or hash maps are created, and recursion is not mentioned, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Start and target cells are the same	If the time is greater than or equal to 1, it's reachable; otherwise, it's unreachable.
Time is insufficient to reach the target, even with the shortest path	Check if the time is less than the Manhattan distance between the start and target cells and return false.
Time is exactly equal to the Manhattan distance	Check if time is exactly equal to the Manhattan distance, meaning no extra moves allowed, and return true.
Time is sufficient to reach the target, but the shortest path requires passing through an obstacle preventing immediate arrival	Since we can move back and forth if time exceeds shortest distance we are always reachable
Integer overflow in calculating Manhattan distance with very large coordinates	Use long data types for calculations to prevent integer overflow.
Coordinates are extremely large, potentially causing performance issues	The constant time Manhattan distance calculation ensures efficient performance regardless of input size.
Either start or target coordinates are negative	The Manhattan distance calculation works correctly with negative coordinates.
Time is very large but the distance is relatively small	Check if the difference between the time and the Manhattan distance is non-negative and even, confirming reachability through repeated back-and-forth movements when time allows.

Start and target cells are the same

How to Handle:

If the time is greater than or equal to 1, it's reachable; otherwise, it's unreachable.

Time is insufficient to reach the target, even with the shortest path

How to Handle:

Check if the time is less than the Manhattan distance between the start and target cells and return false.

Time is exactly equal to the Manhattan distance

How to Handle:

Check if time is exactly equal to the Manhattan distance, meaning no extra moves allowed, and return true.

Time is sufficient to reach the target, but the shortest path requires passing through an obstacle preventing immediate arrival

How to Handle:

Since we can move back and forth if time exceeds shortest distance we are always reachable

Integer overflow in calculating Manhattan distance with very large coordinates

How to Handle:

Use long data types for calculations to prevent integer overflow.

Coordinates are extremely large, potentially causing performance issues

How to Handle:

The constant time Manhattan distance calculation ensures efficient performance regardless of input size.

Either start or target coordinates are negative

How to Handle:

The Manhattan distance calculation works correctly with negative coordinates.

Time is very large but the distance is relatively small

How to Handle:

Check if the difference between the time and the Manhattan distance is non-negative and even, confirming reachability through repeated back-and-forth movements when time allows.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the starting and target cells be the same?
Can the time 't' be zero or negative?
Are the x and y coordinates of the start and end cells integers?
What are the constraints on the magnitude of the x and y coordinates (e.g., maximum or minimum values)?
If it's impossible to reach the target cell within the given time 't', what should I return (e.g., false, 0, or throw an exception)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the starting location.
Imagine you can move up, down, left, or right from your current location.
Consider all possible single moves you can make from the starting location.
For each of those new locations, again consider all possible moves you can make.
Keep repeating this process, keeping track of how long it takes to get to each new location.
If you ever reach the destination, check if the time taken is exactly the time allowed.
If the time is exactly the allowed time, then the destination is reachable.
If you've explored all possible moves for all possible locations within the time limit, and you haven't found a path that leads to the destination in the correct amount of time, then the destination is not reachable.

Code Implementation

def is_reachable_at_time_brute_force(
    start_row,
    start_column,
    finish_row,
    finish_column,
    allowed_time
):
    # Special case: if start and finish are same
    if start_row == finish_row and start_column == finish_column:
        return allowed_time != 0

    queue = [(start_row, start_column, 0)]

    while queue:
        current_row, current_column, current_time = queue.pop(0)

        # Destination check: if destination and time align return True
        if current_row == finish_row and current_column == finish_column:
            if current_time == allowed_time:
                return True
            else:
                continue

        # Time check: Prune paths exceeding allowed_time
        if current_time >= allowed_time:
            continue

        # Explore all 4 directions
        possible_moves = [
            (current_row + 1, current_column),
            (current_row - 1, current_column),
            (current_row, current_column + 1),
            (current_row, current_column - 1),
        ]

        for next_row, next_column in possible_moves:
            queue.append((next_row, next_column, current_time + 1))

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the difference in row and column values between the starting cell and the target cell. These differences tell you how far apart the cells are.
The most efficient way to move is using diagonal steps because they change both the row and column at once.
Find the largest of the row difference and column difference. This value represents the minimum time required to reach the destination because diagonal movements covers both axis at the same time.
If the starting and ending points are the same, the minimum time is considered as two if the allocated time is one, and the answer is true if the allocated time is zero.
Check if the given time is less than the minimum time we calculated. If it is, the target is unreachable.
If the given time is greater or equal to the minimum time, then there's one more check needed.
Subtract the minimum time from the given time. If the remaining time is an even number or zero, the target is reachable. This is because any extra time can be spent by moving back and forth, which consumes 2 units of time per cell.
If the remaining time after subtraction is odd and we can't return to a previous cell for more even subtractions, the target is unreachable.

Code Implementation

def is_reachable_at_time(start_row, start_column, 
    target_row, target_column, given_time):

    row_difference = abs(target_row - start_row)
    column_difference = abs(target_column - start_column)

    #The minimum time required is the max of row and column difference.
    minimum_time_required = max(row_difference, column_difference)

    if start_row == target_row and start_column == target_column:
        # Special case: starting and ending at the same point.
        if given_time == 1:
            return False
        return True

    if given_time < minimum_time_required:
        return False

    remaining_time = given_time - minimum_time_required

    # If remaining time is even, we can always reach the destination.
    if remaining_time % 2 == 0:
        return True
    else:
        #When time is odd, only reachable if min_time > 1.
        if minimum_time_required > 1:
            return True
        else:
            return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Start and target cells are the same	If the time is greater than or equal to 1, it's reachable; otherwise, it's unreachable.
Time is insufficient to reach the target, even with the shortest path	Check if the time is less than the Manhattan distance between the start and target cells and return false.
Time is exactly equal to the Manhattan distance	Check if time is exactly equal to the Manhattan distance, meaning no extra moves allowed, and return true.
Time is sufficient to reach the target, but the shortest path requires passing through an obstacle preventing immediate arrival	Since we can move back and forth if time exceeds shortest distance we are always reachable
Integer overflow in calculating Manhattan distance with very large coordinates	Use long data types for calculations to prevent integer overflow.
Coordinates are extremely large, potentially causing performance issues	The constant time Manhattan distance calculation ensures efficient performance regardless of input size.
Either start or target coordinates are negative	The Manhattan distance calculation works correctly with negative coordinates.
Time is very large but the distance is relatively small	Check if the difference between the time and the Manhattan distance is non-negative and even, confirming reachability through repeated back-and-forth movements when time allows.

Start and target cells are the same

How to Handle:

If the time is greater than or equal to 1, it's reachable; otherwise, it's unreachable.

Time is insufficient to reach the target, even with the shortest path

How to Handle:

Check if the time is less than the Manhattan distance between the start and target cells and return false.

Time is exactly equal to the Manhattan distance

How to Handle:

Check if time is exactly equal to the Manhattan distance, meaning no extra moves allowed, and return true.

Time is sufficient to reach the target, but the shortest path requires passing through an obstacle preventing immediate arrival

How to Handle:

Since we can move back and forth if time exceeds shortest distance we are always reachable

Integer overflow in calculating Manhattan distance with very large coordinates

How to Handle:

Use long data types for calculations to prevent integer overflow.

Coordinates are extremely large, potentially causing performance issues

How to Handle:

The constant time Manhattan distance calculation ensures efficient performance regardless of input size.

Either start or target coordinates are negative

How to Handle:

The Manhattan distance calculation works correctly with negative coordinates.

Time is very large but the distance is relatively small

How to Handle:

Check if the difference between the time and the Manhattan distance is non-negative and even, confirming reachability through repeated back-and-forth movements when time allows.

0/0 GitHub questions completed

0/0 completed