Reaching Points - Leetcode Solution

The Reaching Points problem on LeetCode asks us to find if we can reach a target point (tx, ty) starting from a source point (sx, sy) using only the following two operations:

• Add the coordinates (x, x+y).
• Add the coordinates (x+y, y).

We can assume that the source point (sx, sy) is always (1, 1).

To solve this problem, we can use a recursive approach where we try all possible paths from the source point to the target point.

Let's define a recursive function canReach(sx, sy, tx, ty) that returns true if we can reach the target point (tx, ty) starting from the source point (sx, sy), and false otherwise.

The base case of the recursion is when the source point coincides with the target point (sx == tx and sy == ty). In this case, we can reach the target point, so we return true.

For the recursive case, we try all possible paths from the source point by applying the two operations described above. If any of these paths reaches the target point, we return true. Otherwise, we return false.

Here's the complete Python code implementation of the canReach function:

def canReach(sx, sy, tx, ty): if sx == tx and sy == ty: # Base case: we have reached the target point. return True

if sx > tx or sy > ty:
    # We have gone beyond the target point, so
    # we cannot reach it.
    return False

# Try all possible paths and return true if
# any of them reaches the target point.
return canReach(sx + sy, sy, tx, ty) or canReach(sx, sx + sy, tx, ty)

This algorithm has a time complexity of O(2^(tx+ty)) in the worst case, which is not very efficient. However, we can optimize it using a bottom-up approach with dynamic programming.

We can use a two-dimensional boolean array reachable[i][j] to store whether we can reach the point (i, j) starting from the source point (1, 1). We can initialize the reachable array with reachable[1][1] = True and reachable[i][j] = False for all other points.

Then, we can iteratively compute the value of reachable[i][j] for all points (i, j) such that i <= tx and j <= ty. For each such point, we can set reachable[i][j] to true if it is reachable from any of the previously computed points (i - j, j) or (i, j - i).

Here's the Python code implementation of the dynamic programming approach:

def canReach(sx, sy, tx, ty): # Initialize the reachable array reachable = [[False] * (ty+1) for _ in range(tx+1)] reachable[1][1] = True

# Compute the values of the reachable array
for i in range(1, tx+1):
    for j in range(1, ty+1):
        if i == 1 and j == 1:
            # Already initialized
            continue
        if i >= j and reachable[i-j][j]:
            reachable[i][j] = True
            continue
        if j >= i and reachable[i][j-i]:
            reachable[i][j] = True
            continue

# Return whether the target point is reachable
return reachable[tx][ty]

1