Stokastik

Machine Learning, AI and Programming

LeetCode : Reaching Points

Problem Statement

Solution :

The obvious way is to go with a DFS or BFS like approach. Starting from the point (sx, sy), we can go in two possible directions (sx + sy, sy) and (sx, sx + sy) and then each of these points can go in two possible directions and so on. Note that the paths will form a tree like structure as we are going in either right or upward direction, so we will never encounter the same point twice along a path.

 

Following method uses DFS with recursion to obtain the solution.

class Solution(object):
def reachingPoints(self, sx, sy, tx, ty):
if (sx, sy) == (tx, ty):
return True
elif sx > tx or sy > ty:
return False
else:
return self.reachingPoints(sx + sy, sy, tx, ty) or self.reachingPoints(sx, sy + sy, tx, ty)

We stop whenever we have reached the target (True) or else we have overshoot the target (False).

We can define the time complexity relation to be :

T(s_x, s_y) = T(s_x + s_y, s_y) + T(s_x, s_x + s_y) + c, with T(x, y) = 1 if = t_x" /> or = t_y" />

which is exponential time complexity 2^{\text{min}(t_x - s_x, t_y - s_y)}.

Given that the range of the points sx, sy, tx and ty is in [1, 10^9], it is quite obvious that the above approach will throw "maximum recursion depth reached" or the online judge will throw "Time limit exceeded".

Observe that we can reach a point (tx, ty) from only one point, i.e. if tx >= ty, then we can jump from (tx - ty, ty) to (tx, ty) else if tx < ty, then we can jump from (tx, ty - tx) to (tx, ty).

Thus instead of going from (sx, sy) to (tx, ty), if we go from (tx, ty) to (sx, sy) then we will reach in linear time.

class Solution(object):
def reachingPoints(self, sx, sy, tx, ty):
if (sx, sy) == (tx, ty):
return True
elif sx > tx or sy > ty:
return False
else:
if tx >= ty:
return self.reachingPoints(sx, sy, tx - ty, ty)
else:
return self.reachingPoints(sx, sy, tx, ty - tx)

The time complexity is now O(\text{min}(t_x - s_x, t_y - s_y)).

Still the worst case complexity is linear, which means if (sx, sy) = (1, 1) and (tx, ty) = (1000000000, 1), then we would   need to cover 1000000000 points even if we know that we will reach (sx, sy) for sure.

To handle the above drawback, instead of jumping only ty from tx or tx from ty in one step, how much can we jump and to what point, so that we can still reach (sx, sy) without overshooting it ?

Let's call this the 'jump_factor'.

= s_x" /> for = t_y" /> and

= s_y" /> for t_x < t_y

The modified code is :

class Solution(object):
def reachingPoints(self, sx, sy, tx, ty):
if (sx, sy) == (tx, ty):
return True
elif sx > tx or sy > ty:
return False
else:
if tx >= ty:
jump_factor = max(int((tx - sx) / ty), 1)
return self.reachingPoints(sx, sy, tx - jump_factor * ty, ty)
else:
jump_factor = max(int((ty - sy) / tx), 1)
return self.reachingPoints(sx, sy, tx, ty - jump_factor * tx)

Note that the jump factor cannot be 0, else we would be stuck in one place, hence that 'max' factor.

 

Categories: PROBLEM SOLVING

Tags: , , , , ,