Reaching Points - Solution & Explanation
Problem Statement
Given four integers sx, sy, tx, and ty, return true if it is possible to convert the point (sx, sy) to the point (tx, ty) through some operations, or false otherwise.
The allowed operation on some point (x, y) is to convert it to either (x, x + y) or (x + y, y).
Example 1:
Input: sx = 1, sy = 1, tx = 3, ty = 5 Output: true Explanation: One series of moves that transforms the starting point to the target is: (1, 1) -> (1, 2) (1, 2) -> (3, 2) (3, 2) -> (3, 5)
Example 2:
Input: sx = 1, sy = 1, tx = 2, ty = 2 Output: false
Example 3:
Input: sx = 1, sy = 1, tx = 1, ty = 1 Output: true
Constraints:
1 <= sx, sy, tx, ty <= 109
Approach Overview
Problem Overview: Starting from a point (sx, sy), you can transform it using two operations: (x, y) → (x + y, y) or (x, y) → (x, x + y). The task is to determine whether these operations can produce the target point (tx, ty).
Approach 1: Recursive Backtracking (Exponential Time)
This approach simulates the process exactly as described in the problem. From (sx, sy), recursively apply both operations and explore the resulting states until either the target (tx, ty) is reached or the coordinates exceed the target values. Because each state branches into two possibilities, the search tree grows quickly and leads to exponential time complexity O(2^k), where k is the number of operations performed. Space complexity is O(k) due to the recursion stack. While this approach demonstrates the mechanics of the transformation well, it becomes infeasible for large coordinates since the search space explodes.
Approach 2: Reverse Operation with Modulo Optimization (O(log n))
The key observation is that the forward process only increases values. Instead of building from (sx, sy), work backward from (tx, ty). If the last move produced (tx, ty), then the previous state must have been either (tx - ty, ty) or (tx, ty - tx). Repeated subtraction simulates reversing the operation, but doing this one step at a time would still be slow for large numbers. A faster trick uses the modulo operator: if tx > ty, replace tx with tx % ty; if ty > tx, replace ty with ty % tx. This compresses many subtraction steps into a single operation, similar to the Euclidean algorithm used for GCD. Continue until either the coordinates match the start point or one coordinate drops below the start. Time complexity becomes O(log(max(tx, ty))) and space complexity is O(1). The solution relies heavily on reasoning about number transitions, which connects naturally with Math and Number Theory patterns.
Recommended for interviews: The reverse modulo approach is what interviewers typically expect. It shows you can transform a brute-force forward simulation into a mathematical reduction problem. Discussing the recursive backtracking approach first demonstrates understanding of the rules, while transitioning to the reverse greedy strategy highlights optimization skills and familiarity with patterns related to Recursion and arithmetic reasoning.
Approach 1: Reverse Operation Approach
The goal could be efficiently approached by reversing the operations. Instead of trying to reach (tx, ty) from (sx, sy), we attempt to determine whether (sx, sy) can be reached from (tx, ty) using reverse operations. This is achieved by repeatedly applying the inverse operations: (x, x+y) can be reverted to (x, y), and (x+y, y) can be reverted to (x, y). The main idea is to use modulus operations when x != y.
This solution uses a loop to apply the reverse operations until tx or ty is reduced to sx or sy. It checks if further reduction is possible using modulus operations, ensuring the feasibility of reaching (sx, sy) based on the remainder. The logic ensures that one either complements the other by reducing one coordinate using the other. This approach is efficient due to its use of modulus operation, providing a quick reduction of the problem space.
Complexity
Time Complexity: O(log(max(tx, ty)))
Space Complexity: O(1)
Approach 2: Recursive Backtracking Approach
Another strategy involves recursive backtracking, where the function makes recursive calls to simulate both directions (x + y, y) and (x, x + y) to reach the target point (tx, ty) from the start point (sx, sy). Although less efficient compared to the reverse operation method due to its depth, it's an introductory way to explore the possibilities.
The backtracking approach uses recursion to simulate both possible moves at each step, verifying if any combination of moves can transition the start point into the target point. However, this implementation will face efficiency issues with larger inputs due to recursive depth and repeated evaluations.
Complexity
Time Complexity: Exponential in the worst case
Space Complexity: Recursive stack size
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Reverse Operation Approach | Time Complexity: O(log(max(tx, ty))) |
| Recursive Backtracking Approach | Time Complexity: Exponential in the worst case |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(2^k) | O(k) | Useful for understanding the forward transformation rules or demonstrating brute-force reasoning in interviews |
| Reverse Operation with Modulo Optimization | O(log(max(tx, ty))) | O(1) | Optimal solution for large coordinates; uses mathematical reduction similar to the Euclidean algorithm |
Video Solution
Reaching Points: Leetcode 780 • Tony Teaches • 9,978 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reaching Points easy or hard?
Reaching Points Python/Java solution
How to solve Reaching Points in O(log n)?
What is the best approach for Reaching Points?
Is Reaching Points asked at Google/Amazon/Meta?
What data structure is used in Reaching Points?
What is the time complexity of Reaching Points?
Ready to solve this problem?
Practice Reaching Points with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor