2849. Determine if a Cell Is Reachable at a Given Time
Here, no need to do actual simulations - as t
and points s, f
can be as great as 10^9
.
(dx,dy)
is the absolute distance of points s and f
.
You just basically check if dx
and dy
are both less than or equal to t
- this represents that the path took the shortest possible path.
There’s an edge case though - so in case s == f
, and t > 0
, return False
.
Code:
Python
class Solution:
def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
dx,dy = abs(sx-fx),abs(sy-fy)
'''
dx+dy == 0 means point is (0,0)
if t == 1, obviously (0,0) can't reach (0,1) or (1,0)
'''
if dx+dy==0:
return t != 1
# if distances are smaller than t -> definitely (fx,fy) can be travelled to by (sx,sy)
# in t steps
return dx<=t and dy<=t
Big O Analysis
- Runtime
There are no loops, simulations, just math - so it’s
O(1)
. - Memory
No linear or non-linear data structures used - so memory is
O(1)
.
— A