Problem of The Day: Reaching Points

3 min read 693 words

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        @cache
        def dp(x, y):
            if x == tx and y == ty:
                return True
            if x > tx or y > ty:
                return False
            op1 = dp(x, x + y)
            op2 = dp(x + y, y)
            return op1 or op2


        return dp(sx, sy)

• time: O(tx * ty)
• space: O(tx * ty)

Editorial

Approach #2: Dynamic Programming [Time Limit Exceeded]

class Solution(object):
    def reachingPoints(self, sx, sy, tx, ty):
        seen = set()
        def search(x, y):
            if (x, y) in seen: return
            if x > tx or y > ty: return
            seen.add((x, y))
            search(x+y, y)
            search(x, x+y)

        search(sx, sy)
        return (tx, ty) in seen

Approach #4: Work Backwards (Modulo Variant) [Accepted]

class Solution(object):
    def reachingPoints(self, sx, sy, tx, ty):
        # Work backwards from target (tx, ty) to source (sx, sy)
        # This is more efficient than working forward because we can use modulo to skip many steps
        
        while tx >= sx and ty >= sy:
            # If both coordinates are equal, we can't make progress (would only add to itself)
            if tx == ty:
                break
            
            # Case 1: tx is larger, meaning we got here by doing (x, y) -> (x+y, y)
            elif tx > ty:
                # If ty > sy, we can subtract ty multiple times from tx using modulo
                # This skips many steps at once instead of subtracting ty one at a time
                if ty > sy:
                    tx %= ty
                # If ty == sy, we can only subtract ty from tx
                # Check if we can reach sx by subtracting ty multiple times
                else:
                    return (tx - sx) % ty == 0
            
            # Case 2: ty is larger, meaning we got here by doing (x, y) -> (x, x+y)
            else:
                # If tx > sx, we can subtract tx multiple times from ty using modulo
                if tx > sx:
                    ty %= tx
                # If tx == sx, we can only subtract tx from ty
                # Check if we can reach sy by subtracting tx multiple times
                else:
                    return (ty - sy) % tx == 0

        # Check if we've reached the source coordinates
        return tx == sx and ty == sy

• time: O(log(max(tx, ty)))
• space: O(1)