How do you solve Reaching Points on LeetCode?

Reaching Points (LeetCode #780) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log(max(tx, ty))) time complexity and O(1) space complexity. Key insight: The operations are reversible, allowing us to work backwards from the target.

What is the brute force solution for Reaching Points?

The brute force approach for Reaching Points is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves trying all possible paths from the starting point (sx, sy) to see if we can reach (tx, ty) using the allowed operations. This is like exploring every possible route on a map to find if a destination is reachable. The optimal Optimal Solution approach improves this to O(log(max(tx, ty))).

What algorithm or data structure is used to solve Reaching Points?

Reaching Points uses the following concepts: Math. The recommended patterns to study are: Mathematical Operations, Greedy Algorithms.

What are the interview tips for Reaching Points?

Think about both forward and backward approaches to problems — sometimes working backwards is easier. Always consider edge cases, such as when the starting point is equal to the target. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Reaching Points?

Failing to consider the reverse operations and only trying to move forward. Not checking the modular conditions after reducing tx and ty.

#780

Reaching Points

Hard

MathMathematical OperationsGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log(max(tx, ty)))
Space	O(1)	O(1)

💡

Intuition

Time O(log(max(tx, ty)))Space O(1)

Instead of trying to reach the target from the start point, we can reverse the operations and check if we can reach the starting point from the target. This is like retracing your steps on a map to see if you can get back to where you started.

⚙️

Algorithm

3 steps

1Step 1: While tx and ty are greater than sx and sy, reverse the operations: if tx > ty, subtract ty from tx; otherwise, subtract tx from ty.
2Step 2: After reducing tx and ty, check if either tx equals sx and ty is greater than or equal to sy, or ty equals sy and tx is greater than or equal to sx.
3Step 3: If we can reach (sx, sy) from (tx, ty) using the reverse operations, return true; otherwise, return false.

solution.py9 lines

1# Full working Python code
2
3def canReach(sx, sy, tx, ty):
4    while tx > sx and ty > sy:
5        if tx > ty:
6            tx -= ty
7        else:
8            ty -= tx
9    return (tx == sx and ty >= sy and (ty - sy) % sx == 0) or (ty == sy and tx >= sx and (tx - sx) % sy == 0)

ℹ

Complexity note: The complexity is O(log(max(tx, ty))) because we are effectively halving the larger of the two coordinates in each iteration, which leads to logarithmic time complexity.

1The operations are reversible, allowing us to work backwards from the target.
2The conditions for reaching the target involve modular arithmetic, which can simplify checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.