Reaching Points

Hard Arrays & Hashing Math / Number Theory Original on LeetCode

Reaching Points is a hard arrays & hashing problem solved with the math / number theory pattern. The best approach, optimal (walk backward with modulo), runs in O(log(max(tx, ty))) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (explore forward) up.

Problem

You start at the point (sx, sy). In one move you may replace the point (x, y) with either (x + y, y) or (x, x + y).

Return true if some sequence of zero or more moves turns (sx, sy) into (tx, ty), and false otherwise.

Examples

Example 1

Input
sx = 2, sy = 3, tx = 8, ty = 11
Output
true
Why
(2, 3) -> (5, 3) -> (8, 3) -> (8, 11): add y twice, then add x once.

Example 2

Input
sx = 3, sy = 3, tx = 10, ty = 12
Output
false
Why
Walking back from (10, 12), the 12 must have come from 12 - 10 = 2, which is already below the start value 3.

Example 3

Input
sx = 4, sy = 1, tx = 4, ty = 1
Output
true
Why
Zero moves are allowed, and the start already equals the target.

Constraints

  • 1 <= sx, sy, tx, ty <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (explore forward)O(tx · ty)O(tx + ty)
Better (walk backward by subtraction)O(max(tx, ty))O(1)
Optimal (walk backward with modulo)O(log(max(tx, ty)))O(1)

1Brute force (explore forward)

TimeO(tx · ty)Each point (x, y) with x <= tx and y <= ty is visited at most once, because the way back from any point is unique.
SpaceO(tx + ty)Recursion depth is the number of moves, at most tx + ty.

From (x, y), try both moves recursively. A branch dies as soon as one coordinate passes its target, since coordinates never shrink.

  1. If x > tx or y > ty, return false.
  2. If (x, y) == (tx, ty), return true.
  3. Return go(x + y, y) or go(x, x + y).
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        return go(sx, sy, tx, ty);
    }

    private boolean go(long x, long y, long tx, long ty) {
        if (x > tx || y > ty) return false;
        if (x == tx && y == ty) return true;
        return go(x + y, y, tx, ty) || go(x, x + y, tx, ty);
    }
}

2Better (walk backward by subtraction)

TimeO(max(tx, ty))When one coordinate is tiny, every step removes only that tiny amount.
SpaceO(1)Only the two coordinates are updated.

Every point has exactly one parent: whichever coordinate is larger was produced by adding the smaller one. Walk back from the target by subtracting the smaller coordinate from the larger one until you drop below the start.

  1. While tx >= sx and ty >= sy:
  2. If (tx, ty) == (sx, sy), return true.
  3. If tx > ty, tx -= ty; else if ty > tx, ty -= tx; else stop (equal coordinates have no parent).
  4. Return false.
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) tx -= ty;
            else if (ty > tx) ty -= tx;
            else break;
        }
        return false;
    }
}

3Optimal (walk backward with modulo)

TimeO(log(max(tx, ty)))Same number of steps as Euclid's algorithm on (tx, ty).
SpaceO(1)Only the two coordinates are updated.

A run of identical subtractions tx -= ty is just tx %= ty, so collapse it, which makes the walk run like Euclid's gcd algorithm. The one catch: once a coordinate equals its start value it must not be reduced further, and the other coordinate is reachable exactly when its excess over the start is a multiple of the fixed coordinate.

  1. While tx > sx and ty > sy: if tx > ty, tx %= ty; else ty %= tx.
  2. If tx == sx: return ty >= sy and (ty - sy) % sx == 0.
  3. If ty == sy: return tx >= sx and (tx - sx) % sy == 0.
  4. Otherwise return false.
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy) {
            if (tx > ty) tx %= ty;
            else ty %= tx;
        }
        if (tx == sx) return ty >= sy && (ty - sy) % sx == 0;
        if (ty == sy) return tx >= sx && (tx - sx) % sy == 0;
        return false;
    }
}

Edge cases to test

  • Start equals target
  • Target smaller than the start in some coordinate
  • One coordinate already matches and the other must be reached by repeated additions
  • Huge targets with a tiny partner coordinate, e.g. (1, 1) to (10^9, 1)

Hints

Hint 1

Going forward there are two choices per move. Going backward from (tx, ty) there is only one: the larger coordinate must have been the one that grew.

Hint 2

Repeatedly subtracting the smaller coordinate from the larger one is slow when they are very different. What does a run of subtractions amount to?

Hint 3

Use % to do many subtractions at once, but stop as soon as one coordinate equals its start value and check the other one with a single divisibility test.

FAQ

What is the best time complexity for Reaching Points?

Optimal (walk backward with modulo) runs in O(log(max(tx, ty))) time and O(1) extra space. Same number of steps as Euclid's algorithm on (tx, ty).

Which pattern does Reaching Points use?

It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Water and Jug Problem, Distribute Candies Among Children II.

Is there a brute force solution for Reaching Points?

Yes. Brute force (explore forward) takes O(tx · ty) time and O(tx + ty) space. From (x, y), try both moves recursively.

Which edge cases should I test for Reaching Points?

Start equals target; Target smaller than the start in some coordinate; One coordinate already matches and the other must be reached by repeated additions; Huge targets with a tiny partner coordinate, e.g. (1, 1) to (10^9, 1).