Jobs

Interviews

Discussions

Reaching Points

Hard

Asked by:

20 views

Topics:

Greedy AlgorithmsRecursion

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 <= 10⁹

Reaching Points

Hard

Asked by:

20 views

Topics:

Greedy AlgorithmsRecursion

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 <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of sx, sy, tx, and ty? Specifically, what are the maximum and minimum possible values, and are negative values allowed?
If it's impossible to reach (tx, ty) from (sx, sy), should I return false, or is there any other specific return value expected in that case?
Are sx, sy, tx, and ty guaranteed to be integers?
If sx equals tx and sy equals ty, should I return true immediately?
Can sx be equal to sy, or tx equal to ty?

Brute Force Solution

Approach

The brute force approach to this problem is like trying to get to a specific location on a map by randomly exploring all possible routes. We'll start from the beginning and keep exploring different paths until we find the destination, or exhaust all possible paths.

Here's how the algorithm would work step-by-step:

Begin at the starting point.
Explore making a move either in one direction (say, increasing one coordinate) or in another direction (increasing the other coordinate).
Keep track of all the locations you've already visited to avoid going in circles.
For each new location, consider your options: make one more move in the first direction or one more move in the second direction.
Continue exploring these paths until you either reach the desired ending location or all possible move combinations have been exhausted.
If you find the ending location along any path, then you know it's reachable.
If you have explored every possible combination of moves from the start and still haven't reached the end, then the destination is unreachable.

Code Implementation

def reaching_points_brute_force(
    start_x, start_y, target_x, target_y
):
    visited_points = set()

    def explore(current_x, current_y):
        # If we've reached the target, return True.
        if current_x == target_x and current_y == target_y:
            return True

        # If we go over target or revisit, stop.
        if (
            current_x > target_x
            or current_y > target_y
            or (current_x, current_y) in visited_points
        ):
            return False

        visited_points.add((current_x, current_y))

        # Explore moving only in the x direction.
        if explore(current_x + current_y, current_y):
            return True

        # Explore moving only in the y direction.
        if explore(current_x, current_y + current_x):
            return True

        return False

    return explore(start_x, start_y)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(sx+sy)) – The brute force approach explores all possible paths by repeatedly adding either the current x or y coordinate to generate new coordinates. In the worst-case scenario, where the difference between target x and start x (sx) and target y and start y (sy) is large, the number of paths to explore grows exponentially. Each step branches into two possibilities, leading to a binary tree-like exploration. Thus, the time complexity is proportional to the number of nodes in this implicit tree, which is O(2^(sx+sy)) because each branch corresponds to either increasing the x or y coordinate.

Space Complexity

O(2^(s+t)) – The brute force approach explores all possible paths from the start point (s, t) using recursion. The algorithm keeps track of visited locations to avoid cycles. In the worst case, the number of possible locations to explore grows exponentially with the sum of the target coordinates. Therefore, the space complexity is dominated by the size of the visited locations set, potentially reaching O(2^(s+t)), since in the worst case the recursion tree and the visited set might grow exponentially with the sum of target coordinates.

Optimal Solution

Approach

Instead of starting at the beginning and trying to reach the target, the optimal solution works backward from the target. By repeatedly subtracting the smaller value from the larger, we effectively reverse the transformation process. This allows us to reach the starting point more efficiently.

Here's how the algorithm would work step-by-step:

Begin with the target point and work backward towards the starting point.
If the target x-coordinate is larger than the target y-coordinate, reduce the x-coordinate by the y-coordinate. If the target y-coordinate is larger, reduce the y-coordinate by the x-coordinate.
Repeat this process until either the x-coordinate or y-coordinate of the current point equals the corresponding coordinate of the starting point.
When one coordinate matches, check if it's possible to reach the other starting coordinate by subtracting the common coordinate from the other target coordinate and seeing if the difference is divisible by it's corresponding starting coordinate. (For example if the target x coordinate is 7 and the starting x coordinate is 4 and the y coordinates are equal, then we see if (7-4) % 4 == 0).
If at any point either coordinate becomes smaller than the corresponding starting coordinate, it's not possible to reach the target.
If you successfully reach the starting point, the target is reachable. Otherwise, it is not.

Code Implementation

def reaching_points(start_x, start_y, target_x, target_y):
    while target_x >= start_x and target_y >= start_y:
        if target_x == start_x and target_y == start_y:
            return True

        if target_x > target_y:
            # Reduce target_x by target_y
            if target_y == start_y:
                return (target_x - start_x) % start_y == 0
            target_x %= target_y

        else:
            # Reduce target_y by target_x
            if target_x == start_x:
                return (target_y - start_y) % start_x == 0
            target_y %= target_x

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log(max(tx, ty))) – The algorithm works backward from the target (tx, ty) towards the starting point (sx, sy) by repeatedly subtracting the smaller coordinate from the larger one. In each step, at least one of the target coordinates is reduced. The number of subtractions is logarithmic with respect to the larger of tx and ty because the larger value is being reduced by at least the smaller value on each iteration, similar to the Euclidean algorithm for finding the greatest common divisor. Therefore, the time complexity is O(log(max(tx, ty))).

Space Complexity

O(1) – The algorithm works backward from the target point, modifying the target coordinates in place. It does not create any auxiliary data structures like lists, hash maps, or recursion stack frames. Only a few constant-size variables are used to store the current x and y coordinates while iterating toward the starting point. Therefore, the space complexity is independent of the magnitude of the input coordinates and remains constant.

Edge Cases

Case	How to Handle
sx > tx or sy > ty	Return false immediately, as we can only increase the values.
sx == tx and sy == ty	Return true immediately as the start and target are the same.
tx == sx and ty > sy	Check if (ty - sy) % sx == 0 to see if it can be reached by repeated (x, x+y) transforms.
ty == sy and tx > sx	Check if (tx - sx) % sy == 0 to see if it can be reached by repeated (x+y, y) transforms.
sx or sy are very large (close to max integer)	Consider potential integer overflow during intermediate calculations and use appropriate data types.
tx and ty are equal	The algorithm needs to handle cases where both target values are the same after some transformations.
The algorithm gets stuck in a loop	The reverse calculation approach avoids loops.
tx or ty reaches zero or negative values during the calculation	This should not happen if starting from positive sx and sy and moving backwards, but check to be sure.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of sx, sy, tx, and ty? Specifically, what are the maximum and minimum possible values, and are negative values allowed?
If it's impossible to reach (tx, ty) from (sx, sy), should I return false, or is there any other specific return value expected in that case?
Are sx, sy, tx, and ty guaranteed to be integers?
If sx equals tx and sy equals ty, should I return true immediately?
Can sx be equal to sy, or tx equal to ty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the starting point.
Explore making a move either in one direction (say, increasing one coordinate) or in another direction (increasing the other coordinate).
Keep track of all the locations you've already visited to avoid going in circles.
For each new location, consider your options: make one more move in the first direction or one more move in the second direction.
Continue exploring these paths until you either reach the desired ending location or all possible move combinations have been exhausted.
If you find the ending location along any path, then you know it's reachable.
If you have explored every possible combination of moves from the start and still haven't reached the end, then the destination is unreachable.

Code Implementation

def reaching_points_brute_force(
    start_x, start_y, target_x, target_y
):
    visited_points = set()

    def explore(current_x, current_y):
        # If we've reached the target, return True.
        if current_x == target_x and current_y == target_y:
            return True

        # If we go over target or revisit, stop.
        if (
            current_x > target_x
            or current_y > target_y
            or (current_x, current_y) in visited_points
        ):
            return False

        visited_points.add((current_x, current_y))

        # Explore moving only in the x direction.
        if explore(current_x + current_y, current_y):
            return True

        # Explore moving only in the y direction.
        if explore(current_x, current_y + current_x):
            return True

        return False

    return explore(start_x, start_y)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with the target point and work backward towards the starting point.
If the target x-coordinate is larger than the target y-coordinate, reduce the x-coordinate by the y-coordinate. If the target y-coordinate is larger, reduce the y-coordinate by the x-coordinate.
Repeat this process until either the x-coordinate or y-coordinate of the current point equals the corresponding coordinate of the starting point.
When one coordinate matches, check if it's possible to reach the other starting coordinate by subtracting the common coordinate from the other target coordinate and seeing if the difference is divisible by it's corresponding starting coordinate. (For example if the target x coordinate is 7 and the starting x coordinate is 4 and the y coordinates are equal, then we see if (7-4) % 4 == 0).
If at any point either coordinate becomes smaller than the corresponding starting coordinate, it's not possible to reach the target.
If you successfully reach the starting point, the target is reachable. Otherwise, it is not.

Code Implementation

def reaching_points(start_x, start_y, target_x, target_y):
    while target_x >= start_x and target_y >= start_y:
        if target_x == start_x and target_y == start_y:
            return True

        if target_x > target_y:
            # Reduce target_x by target_y
            if target_y == start_y:
                return (target_x - start_x) % start_y == 0
            target_x %= target_y

        else:
            # Reduce target_y by target_x
            if target_x == start_x:
                return (target_y - start_y) % start_x == 0
            target_y %= target_x

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
sx > tx or sy > ty	Return false immediately, as we can only increase the values.
sx == tx and sy == ty	Return true immediately as the start and target are the same.
tx == sx and ty > sy	Check if (ty - sy) % sx == 0 to see if it can be reached by repeated (x, x+y) transforms.
ty == sy and tx > sx	Check if (tx - sx) % sy == 0 to see if it can be reached by repeated (x+y, y) transforms.
sx or sy are very large (close to max integer)	Consider potential integer overflow during intermediate calculations and use appropriate data types.
tx and ty are equal	The algorithm needs to handle cases where both target values are the same after some transformations.
The algorithm gets stuck in a loop	The reverse calculation approach avoids loops.
tx or ty reaches zero or negative values during the calculation	This should not happen if starting from positive sx and sy and moving backwards, but check to be sure.