Abstract / Summary

Given a grid, a start cell, and a time, decide if a specific cell can be reached at exactly that time by moving according to the grid's rules.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 37% (200k+ submissions).

Typical patterns to solve this problem:

• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether a piece can move from a start coordinate (sx, sy) to a target coordinate (fx, fy) within exactly t time steps on a grid where a move can change either the x-coordinate, the y-coordinate, or both by at most one unit per step. The logic is concise, relying on a few arithmetic operations and early returns to reach a decision in constant time.

Key Steps

Handling the trivial case where start and finish coincide

When the source and destination are identical, the only way to satisfy the movement constraint is to stay in place. The code treats this situation specially because a single time step would force a move, which is prohibited when the positions are already the same.

if sx == fx and sy == fy:
    return t != 1   # impossible with only one move

The condition t != 1 captures the fact that any number of steps other than one can be spent oscillating (for example, moving away and back) while ending at the original location.

Computing the minimal number of steps required

If the start and finish differ, the algorithm computes the shortest possible number of moves using the Chebyshev distance, which is appropriate for a grid where diagonal moves are allowed. This distance is the maximum of the absolute differences in the x and y directions.

distance = max(abs(sx - fx), abs(sy - fy))

Comparing the minimal distance with the allowed time

The final decision is a simple comparison: if the minimal distance does not exceed the allotted time t, the target is reachable; otherwise it is not.

return distance <= t

Edge Cases Addressed

The code explicitly handles the scenario where the start and finish positions are the same. In that case, a single time step would require a move, which would leave the piece off the target, so the function returns False for t == 1. For any other t (including zero), the function correctly returns True because the piece can remain stationary or perform a “ping-pong” sequence that returns to the original cell.

Another implicit edge case is when the required Chebyshev distance is zero (i.e., the positions match) but t is greater than one. The early return for the equal-position case ensures that the function does not mistakenly evaluate the distance comparison, which would otherwise yield True for any t >= 0. This distinction preserves the intended semantics for the single-step impossibility.

When the start and finish differ, the algorithm gracefully handles large coordinate differences because it uses only absolute value and max operations, which are well-defined for any integer inputs within the language’s range.

Performance Optimizations

The implementation achieves optimal performance by avoiding any loops, recursion, or auxiliary data structures. All operations-comparisons, absolute value calculations, and a single max call-execute in constant time. The early return for the equal-position case prevents unnecessary arithmetic when the answer can be determined immediately, saving a few CPU cycles. By using the Chebyshev distance directly, the code eliminates the need for separate handling of horizontal, vertical, and diagonal moves, consolidating the logic into a single arithmetic expression.

Overall, the function runs in O(1) time with O(1) additional space, delivering a decision instantly regardless of the magnitude of the input coordinates.

Imagine a little robot standing on a big grid of squares, like a game board. The robot is at a place called sx and sy, and it wants to visit a destination at fx and fy. The number t tells us exactly how many steps the robot must take to get there.

First, look at the special case where the start and the destination are the exact same square. If the robot has to finish after one single step, it is stuck because it would have to move away and could not get back in time. If the time is anything else, the robot can just hop to a neighbor and hop right back until the time runs out, so it will be at the starting spot again.

For any other place the robot wants to go, there is a path that takes the shortest amount of time. Because the robot can move sideways, up and down, and even diagonally, the minimum number of steps to reach the finish is simply the biggest gap between where the robot starts and where it wants to end, comparing the difference in the x direction and the y direction. As long as the robot has at least that many steps to work with, it can always find a way to land on the target square by moving in a straight line toward the goal and then just waiting nearby if some extra time is left.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java		C++			Python	TS
	WalkCCC	Java		C++			Python
	leetcode.ca	Java		C++	C#	Go	Python	TS
	Progiez	Java		C++			Python
github	charles-wangkai	Java
	fsq		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality