780. Reaching Points
Problem Description
The problem presents an operation that can transform a point (x, y)
in a two-dimensional grid to either (x, x + y)
or (x + y, y)
. Given four integers sx
, sy
, tx
, and ty
, which represent the starting point (sx, sy)
and the target point (tx, ty)
, the task is to determine if it is possible to reach the target point from the starting point by repeatedly applying the transformation.
The only allowed operations are:
- Add the current
y
value to thex
value, changing(x, y)
to(x + y, y)
. - Add the current
x
value to they
value, changing(x, y)
to(x, x + y)
.
The key challenge is to figure out if, by applying these operations starting from (sx, sy)
, we can eventually obtain the point (tx, ty)
. If it's possible, return true
; otherwise, return false
.
Intuition
To solve this problem, we can use the reverse thinking approach. Instead of starting from (sx, sy)
and trying to reach (tx, ty)
using the allowed operations, we start from (tx, ty)
and try to work our way backwards to (sx, sy)
. This approach is valid because the operations are reversible.
We repeatedly subtract the smaller of tx
and ty
from the larger until we either pass sx
and sy
or land exactly on them. During this process, if tx
is greater than ty
, we know that tx
had to be formed by adding ty
to a smaller number in the previous step, so we perform tx %= ty
. The same reasoning applies if ty
is greater than tx
.
While doing this, there are three cases:
- If both
tx
andty
are greater thansx
andsy
respectively, we continue reducingtx
andty
. - If
tx
becomes equal tosx
, we check ifty
can be reduced tosy
by a multiple oftx
. If so, it means we can reach(sx, sy)
from(tx, ty)
. - The same check applies if
ty
becomes equal tosy
.
If none of the conditions are met, then it's not possible to transform (sx, sy)
to (tx, ty)
using the operations, so we return false
.
The time complexity of this approach is O(log(max(tx, ty))), which occurs due to the modulo operation that reduces tx
and ty
exponentially.
Learn more about Math patterns.
Solution Approach
The implementation of the solution follows a reverse approach working backward from the target point (tx, ty)
to the start point (sx, sy)
. Here's how the solution translates into code:
-
The solution starts by initializing a while loop that continues as long as both
tx
andty
are larger thansx
andsy
, buttx
is not equal toty
. This condition allows us to reducetx
andty
until either we can't reduce them anymore without going belowsx
orsy
, or until one of the coordinates matchessx
orsy
. -
Inside the loop, we use the
%
(modulo) operator to reverse the operation as follows:-
If
tx > ty
, thentx
must have been formed by adding some multiple ofty
to the previousx
value, so we performtx %= ty
. This reverses the last operation that affectedtx
. -
If
ty > tx
, then we applyty %= tx
for the same reason but in the vertical direction.
-
-
After exiting the loop, either
tx == sx
and/orty == sy
, or bothtx
andty
have been reduced belowsx
andsy
. We need to handle both cases to complete the algorithm:-
If
tx == sx
andty == sy
at the same time, we've found the exact reverse path to(sx, sy)
, and the function returnstrue
. -
If
tx == sx
, thenty
must be reducible tosy
by repeatedly subtractingtx
(the same operation reversed). We check this by ensuringty > sy
and(ty - sy) % tx == 0
. If this is the case, we returntrue
. -
Similarly, if
ty == sy
, we check iftx > sx
and(tx - sx) % ty == 0
to determine iftx
can be reduced tosx
and returntrue
accordingly.
-
-
If none of the conditions are met, it means that we can't reach
(sx, sy)
from(tx, ty)
by reversing the operations, so the function returnsfalse
.
This approach is efficient because it avoids the exponential time complexity of trying all possible paths from (sx, sy)
to (tx, ty)
. Instead, by taking advantage of the mathematical properties of the operation, it quickly navigates to the solution or determines impossibility with a time complexity of O(log(max(tx, ty)))
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the problem with a small example:
Imagine our starting point is (sx, sy) = (2, 4)
and our target point is (tx, ty) = (9, 4)
. Can we transform the starting point to the target point using the allowed operations?
We apply the reverse approach:
- We start from
(tx, ty)
which is(9, 4)
and compare it with(sx, sy)
. Sincetx > ty
, we performtx %= ty
. - After applying the modulo operation,
tx
is now9 % 4 = 1
. - Now, our target point
(tx, ty)
has changed to(1, 4)
. - We compare
tx
withsx
. They are not equal, so we continue with the loop. - Since
ty > tx
, we performty %= tx
. - After applying the modulo operation,
ty
is now4 % 1 = 0
. The target point is now(1, 0)
. - Comparing the new
ty
withsy
, we see thatty < sy
; we cannot reducety
anymore without going belowsy
.
From the example above, we note the following:
- After several steps, we've ended up with
ty < sy
, which violates the condition that it's only possible to either match the starting point exactly (in which case bothtx
andty
would matchsx
andsy
) or reduce one of the target coordinates to match the starting point's while checking if the other can achieve the same via multiples. - Since we could not achieve a situation where
tx
orty
matchessx
orsy
respectively without the other target coordinate going below its starting counterpart, it proves that the path from(sx, sy)
to(tx, ty)
cannot be achieved with the given operations. - As a result, we would return
false
for this example.
Key Takeaways:
- The reverse approach significantly simplifies the problem, turning an otherwise computationally expensive search into a series of simple subtraction operations (modulo operation).
- If at any point during the reverse operation one of the target coordinates becomes less than its corresponding start coordinate, we can stop and return
false
because this means that the target point cannot be reached from the starting point.
Solution Implementation
1class Solution:
2 def reachingPoints(self, start_x: int, start_y: int, target_x: int, target_y: int) -> bool:
3 # Loop to transform the target point back towards the starting point
4 while target_x > start_x and target_y > start_y and target_x != target_y:
5 # If target_x is greater than target_y, reduce target_x
6 if target_x > target_y:
7 # The modulo operation finds how many steps can be taken from target_y to reach current target_x
8 target_x %= target_y
9 # If target_y is greater than target_x, reduce target_y
10 else:
11 # Likewise, this modulo operation finds the steps from target_x to reach current target_y
12 target_y %= target_x
13
14 # Check if the starting point is reached after breaking out of the loop
15 if target_x == start_x and target_y == start_y:
16 return True
17
18 # If only target_x matches start_x, check if we can reach the target point
19 # by repeatedly subtracting start_x from target_y
20 if target_x == start_x:
21 return target_y > start_y and (target_y - start_y) % target_x == 0
22
23 # If only target_y matches start_y, check if we can reach the target point
24 # by repeatedly subtracting start_y from target_x
25 if target_y == start_y:
26 return target_x > start_x and (target_x - start_x) % target_y == 0
27
28 # If neither target_x nor target_y matches, reaching the target point is not possible
29 return False
30
1class Solution {
2
3 /**
4 * Checks if a point (sx, sy) can reach (tx, ty) by moving either vertically or horizontally.
5 *
6 * @param sx Starting point x-coordinate.
7 * @param sy Starting point y-coordinate.
8 * @param tx Target point x-coordinate.
9 * @param ty Target point y-coordinate.
10 * @return True if the starting point can reach the target point, else false.
11 */
12 public boolean reachingPoints(int startX, int startY, int targetX, int targetY) {
13 // Work backwards from the target point to the starting point.
14 while (targetX > startX && targetY > startY && targetX != targetY) {
15 if (targetX > targetY) {
16 // If the current x-coordinate is larger, reduce it modulo the y-coordinate.
17 targetX %= targetY;
18 } else {
19 // If the current y-coordinate is larger or equal, reduce it modulo the x-coordinate.
20 targetY %= targetX;
21 }
22 }
23
24 // If we have reached the starting point, return true.
25 if (targetX == startX && targetY == startY) {
26 return true;
27 }
28
29 // If we are in the same horizontal line as the starting point, check if we can reach by vertical moves.
30 if (targetX == startX) {
31 return targetY > startY && (targetY - startY) % startX == 0;
32 }
33
34 // If we are in the same vertical line as the starting point, check if we can reach by horizontal moves.
35 if (targetY == startY) {
36 return targetX > startX && (targetX - startX) % targetY == 0;
37 }
38
39 // If none of the above conditions are met, the target cannot be reached from the starting point.
40 return false;
41 }
42}
43
1class Solution {
2public:
3 // Function to determine if we can reach the point (tx, ty) starting at (sx, sy)
4 bool reachingPoints(int startX, int startY, int targetX, int targetY) {
5 // Run the loop until either of the target co-ordinates is greater than the start co-ordinates
6 // and they are not the same. This is because we can move from (x, y) to (x, x+y) or (x+y, y),
7 // not the other way around.
8 while (targetX > startX && targetY > startY && targetX != targetY) {
9 // If targetX is greater than targetY, we know in the last move targetX was changed.
10 // So we take modulus to revert the last operation and try the previous state.
11 if (targetX > targetY) {
12 targetX %= targetY;
13 }
14 // Similarly, if targetY is greater, we find the previous state of targetY by taking modulus.
15 else {
16 targetY %= targetX;
17 }
18 }
19
20 // If we have exactly reached the start point, return true.
21 if (targetX == startX && targetY == startY) return true;
22
23 // If the targetX is the same as startX, then we can only reach the target by vertical moves.
24 // Thus, check if the difference is a multiple of startX.
25 if (targetX == startX) return targetY > startY && (targetY - startY) % targetX == 0;
26
27 // If the targetY is the same as startY, then we can only reach the target by horizontal moves.
28 // Thus, check if the difference is a multiple of startY.
29 if (targetY == startY) return targetX > startX && (targetX - startX) % targetY == 0;
30
31 // If neither of the above cases, we can't reach the target point with the moves allowed.
32 return false;
33 }
34};
35
1// Function to determine if we can reach the point (targetX, targetY) starting at (startX, startY)
2function reachingPoints(startX: number, startY: number, targetX: number, targetY: number): boolean {
3 // Run the loop until either of the target coordinates is greater than the start coordinates
4 // and they are not the same. This is because we can move from (x, y) to (x, x+y) or (x+y, y),
5 // not the other way around.
6 while (targetX > startX && targetY > startY && targetX !== targetY) {
7 // If targetX is greater than targetY, we know in the last move targetX was changed.
8 // So we take modulus to revert the last operation and try the previous state.
9 if (targetX > targetY) {
10 targetX %= targetY;
11 }
12 // Similarly, if targetY is greater, we find the previous state of targetY by taking modulus.
13 else {
14 targetY %= targetX;
15 }
16 }
17
18 // If we have exactly reached the start point, return true.
19 if (targetX === startX && targetY === startY) return true;
20
21 // If the targetX is the same as startX, then we can only reach the target by vertical moves.
22 // Thus, check if the difference is a multiple of startX.
23 if (targetX === startX) return targetY > startY && (targetY - startY) % startX === 0;
24
25 // If the targetY is the same as startY, then we can only reach the target by horizontal moves.
26 // Thus, check if the difference is a multiple of startY.
27 if (targetY === startY) return targetX > startX && (targetX - startX) % startY === 0;
28
29 // If neither of the above cases, we can't reach the target point with the moves allowed.
30 return false;
31}
32
Time and Space Complexity
Time Complexity
The time complexity of the provided code primarily depends on the number of iterations it takes for either tx
or ty
to be reduced to either sx
or sy
, or for tx
to equal ty
. In each iteration, either tx
or ty
is reduced by a modulo operation, which takes constant time. However, the number of iterations could be large if tx
and ty
are much larger than sx
and sy
.
In the worst case, the modulo operation reduces the larger number by an amount proportional to the smaller number. Therefore, the time complexity is logarithmic in relation to the difference between the target and the start coordinates, or more formally, O(log(max(tx - sx, ty - sy)))
.
Space Complexity
The space complexity of the provided code is O(1)
. This is because the algorithm only uses a fixed amount of additional space (for variables tx
and ty
), and there is no additional space usage that grows with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!