We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Determine if a Cell Is Reachable at a Given Time

Number: 3056

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given starting coordinates (sx, sy) and target coordinates (fx, fy) on an infinite 2D grid, along with a non-negative integer t that represents seconds, determine whether it is possible to reach the target cell in exactly t seconds. At every second, you must move to one of the 8 adjacent cells (vertical, horizontal, or diagonal). Cells may be visited multiple times.

Key Insights

  • The movement allowed is equivalent to a king’s move in chess.
  • The minimum number of moves required to travel from the start to the finish is given by the Chebyshev distance: max(|fx - sx|, |fy - sy|).
  • If t is less than this minimum distance, reaching the target in exactly t seconds is impossible.
  • When t is greater than or equal to the minimum required moves, extra moves can be absorbed by taking detours (since any move must change position, one can always insert a two-move detour).
  • There’s no parity constraint because the 8-directional moves allow flexible change in parity.

Space and Time Complexity

Time Complexity: O(1) – only arithmetic operations and comparisons are performed. Space Complexity: O(1) – a constant amount of extra space is used.

Solution

The algorithm works by first calculating the Chebyshev distance between the start and finish points. This distance represents the minimum number of seconds needed if moving optimally (for example, using diagonal moves to cover both dimensions at once). If the given time t is less than this distance, return false because it is impossible to reach the target in time. Otherwise, return true because extra moves can always be incorporated into the path, using detours if necessary.

Data Structures used:

  • Simple integer variables for holding coordinates and differences.

Algorithmic Approach:

  1. Calculate dx = |fx - sx| and dy = |fy - sy|.
  2. Compute requiredMoves = max(dx, dy).
  3. If t is less than requiredMoves, it is impossible to reach (return false).
  4. Otherwise, it is always possible to design a route taking exactly t moves (return true).

Code Solutions

# Calculate whether the target cell is reachable in exactly t seconds.
def isReachable(sx, sy, fx, fy, t):
    # Compute the differences in the x and y coordinates.
    dx = abs(fx - sx)
    dy = abs(fy - sy)
    # Compute the minimum moves required (Chebyshev distance).
    required_moves = max(dx, dy)
    # Check if we have at least the minimum required moves.
    if t < required_moves:
        return False
    # We can always use extra moves as detours.
    return True

# Example usage:
print(isReachable(2, 4, 7, 7, 6))  # Expected output: True
print(isReachable(3, 1, 7, 3, 3))  # Expected output: False
← Back to All Questions