LeetCode 3609 - Minimum Moves to Reach Target in Grid

LeetCode Problem 3609

Difficulty: 🔴 Hard
Topics: Math

Solution

Problem Understanding

The problem asks us to determine the minimum number of moves to reach a target point (tx, ty) from a starting point (sx, sy) on an infinite 2D grid. The movement rules are specific: from any point (x, y), you can move either right by max(x, y) units or up by max(x, y) units. That means each move depends on the current coordinates, not a fixed step size.

The input consists of four integers representing the coordinates of the start and target points. The output is an integer representing the minimum number of moves to reach the target, or -1 if it is impossible. The constraints 0 <= sx <= tx <= 10^9 and 0 <= sy <= ty <= 10^9 imply that brute-force exploration of all paths is infeasible due to the potentially enormous coordinate values.

Key edge cases include situations where either coordinate of the start is initially zero, where the target is unreachable due to the movement rules, and where sx = tx or sy = ty, which could allow moves in only one dimension.

The challenge is that the movement is multiplicative in effect, as each move jumps by max(x, y), so naive BFS or DFS would quickly become inefficient. Recognizing patterns in reachable coordinates and working backwards from the target can lead to an efficient solution.

Approaches

The brute-force approach would be a BFS starting from (sx, sy). At each step, we would enqueue (x + max(x, y), y) and (x, y + max(x, y)). While this guarantees correctness, it is impractical due to the exponential growth of states and the large range of coordinates up to 10^9.

The optimal approach relies on working backwards from (tx, ty) to (sx, sy). Observing the movement rules, the only way to have reached (tx, ty) in the last move is either from (tx - ty, ty) if tx > ty, or (tx, ty - tx) if ty > tx. This is similar to the Euclidean algorithm for greatest common divisor. We repeatedly subtract the smaller coordinate from the larger one until we reach (sx, sy) or determine it is impossible. The move count can be tracked by counting each subtraction operation. This ensures efficiency because the number of steps is logarithmic relative to the distance between the coordinates.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(2^n)	BFS exploring all reachable points; infeasible for large coordinates
Optimal	O(log(max(tx, ty)))	O(1)	Backward subtraction method; similar to Euclidean GCD, efficient and scalable

Algorithm Walkthrough

1. Initialize a move counter to zero.
2. While (tx, ty) is not equal to (sx, sy), do the following:

a. If tx < sx or ty < sy, return -1 because the target is unreachable.

b. If tx == ty, return -1 because no move can reach (tx, ty) if both coordinates are equal but not equal to (sx, sy).

c. If tx > ty, we know the last move increased the x-coordinate by max(previous_x, previous_y). Therefore, subtract multiples of ty from tx while tx > sx, and increment the move counter by the number of subtractions.

d. If ty > tx, we do the analogous operation for the y-coordinate, subtracting multiples of tx from ty and updating the move counter. 3. If after the loop (tx, ty) equals (sx, sy), return the move counter. Otherwise, return -1.

Why it works: The backward subtraction preserves the invariant that each step could have been a valid move from the previous position, and the process always reduces one coordinate towards the start. This ensures we never explore invalid states, and the logarithmic reduction guarantees efficiency. This problem describes an infinite 2D grid where you start from a point (sx, sy) and want to reach (tx, ty) using a very specific movement rule. At any position (x, y), you compute m = max(x, y) and you are allowed to move in exactly one of two ways: you can either add m to the x-coordinate or add m to the y-coordinate. This means each move depends dynamically on the current state of the point, and the growth is multiplicative-like because the increment is tied to the larger coordinate.

The task is to determine the minimum number of such moves required to reach the target point exactly. If it is impossible to reach the target, the function must return -1.

The constraints indicate that coordinates can be as large as 10^9, which immediately rules out any brute-force exploration of states. The grid is infinite, so there is no natural boundary to constrain search either. This strongly suggests that the solution must be greedy or reverse-engineered rather than forward simulated.

Several edge cases are important. If (sx, sy) is already equal to (tx, ty), the answer is zero. If either coordinate of the start already exceeds the target, the answer is immediately impossible because all moves only increase coordinates. Another subtle case arises when both coordinates are equal or become equal, because the move behavior becomes symmetric and can lead to ambiguity in reverse reasoning.

Approaches

The brute-force approach would attempt a breadth-first search starting from (sx, sy), exploring both possible transitions at every step. While this would eventually find the shortest path, each state branches into two more states, and coordinates grow rapidly. Because values can reach up to 10^9, the state space becomes astronomically large, making this approach infeasible both in time and memory.

The key insight is to reverse the process. Instead of trying to go from (sx, sy) to (tx, ty), we work backward from (tx, ty) to (sx, sy). In reverse, we try to determine which previous state could have generated the current one. Each forward move either adds the maximum coordinate to x or to y, so in reverse we try to subtract or undo that operation.

A crucial observation is that at each step, only the larger coordinate could have been increased in a meaningful way. If one coordinate is significantly larger than the other, we can often infer whether it was formed by repeated doubling or by additive operations. This leads to a greedy reduction strategy where we always reduce the larger coordinate in a way that preserves validity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force BFS	O(2^(tx+ty))	O(2^(tx+ty))	Expands both moves forward, completely infeasible
Reverse Greedy	O(log max(tx, ty))	O(1)	Work backward from target by reducing larger coordinate

Algorithm Walkthrough

The optimal solution works backward from (tx, ty) until we either reach (sx, sy) or determine it is impossible.

1. We initialize a counter for the number of reverse steps and set our current position to (tx, ty). The idea is that every reverse operation corresponds to one forward move in the original path.
2. We repeatedly reduce the larger of the two coordinates. This is because in the forward process, only the larger coordinate determines the increment size, so the reverse process must undo transformations from the dominant dimension.
3. If tx > ty, we analyze whether the last operation likely came from doubling x or adding x to y. If tx is at least twice ty, it is safe to assume repeated doubling occurred, so we divide tx by 2 when it is even. Otherwise, we subtract ty from tx, which corresponds to reversing a y += x type operation.
4. Symmetrically, if ty > tx, we apply the same reasoning in reverse for the y-dimension.
5. We stop early if either coordinate matches the starting coordinates. At that point, we check if the remaining dimension can be reduced to match the start exactly using valid additive reversals.
6. If at any point we encounter an invalid state (such as requiring a subtraction that does not align with the rules), we return -1.

Why it works

The correctness relies on the invariant that every forward move strictly increases one coordinate by the current maximum of the two coordinates. This means the structure of growth is monotonic and dominated by the larger coordinate. By always reducing the larger coordinate in reverse, we ensure we are undoing the most recent valid transformation. This greedy choice is safe because any alternative reverse path would either violate monotonic constraints or lead to a larger number of steps.

Python Solution

class Solution:
    def minMoves(self, sx: int, sy: int, tx: int, ty: int) -> int:
        moves = 0
        while tx >= sx and ty >= sy:
            if tx == sx and ty == sy:
                return moves
            if tx == ty:
                return -1
            if tx > ty:
                if ty > sy:
                    count = (tx - sx) // ty
                    if count == 0:
                        count = 1
                    tx -= count * ty
                    moves += count
                else:
                    # ty == sy, subtract only once if possible
                    if (tx - sx) % ty == 0:
                        moves += (tx - sx) // ty
                        return moves
                    else:
                        return -1
            else:  # ty > tx
                if tx > sx:
                    count = (ty - sy) // tx
                    if count == 0:
                        count = 1
                    ty -= count * tx
                    moves += count
                else:
                    if (ty - sy) % tx == 0:
                        moves += (ty - sy) // tx
                        return moves
                    else:
                        return -1
        return -1

This Python implementation directly follows the backward reduction logic. At each iteration, we reduce the larger coordinate while counting moves. Special handling occurs when one of the coordinates matches the start, in which case we check if exact multiples exist to reach the target. if sx == tx and sy == ty: return 0

    if sx > tx or sy > ty:
        return -1

    moves = 0

    while tx > sx or ty > sy:
        if tx == ty:
            break

        if tx > ty:
            if ty == sy:
                if (tx - sx) % ty != 0:
                    return -1
                return moves + (tx - sx) // ty
            if tx >= 2 * ty:
                if tx % 2 != 0:
                    return -1
                tx //= 2
            else:
                tx -= ty
            moves += 1
        else:
            if sx == tx:
                if (ty - sy) % tx != 0:
                    return -1
                return moves + (ty - sy) // tx
            if ty >= 2 * tx:
                if ty % 2 != 0:
                    return -1
                ty //= 2
            else:
                ty -= tx
            moves += 1

    if tx == sx and ty == sy:
        return moves

    if tx == sx:
        if ty < sy or (ty - sy) % tx != 0:
            return -1
        return moves + (ty - sy) // tx

    if ty == sy:
        if tx < sx or (tx - sx) % ty != 0:
            return -1
        return moves + (tx - sx) // ty

    return -1

The implementation starts with feasibility checks, ensuring we never try to reach a target that is already smaller than the starting point in any dimension. It then repeatedly reduces the larger coordinate using either halving or subtraction logic depending on whether a doubling pattern is likely. Once one coordinate aligns with the start, it verifies whether the remaining coordinate can be matched exactly through valid repeated reverse additions.

## Go Solution

```go
func minMoves(sx int, sy int, tx int, ty int) int {
    moves := 0
    for tx >= sx && ty >= sy {
        if tx == sx && ty == sy {
            return moves
        }
        if tx == ty {
            return -1
        }
        if tx > ty {
            if ty > sy {
                count := (tx - sx) / ty
                if count == 0 {
                    count = 1
                }
                tx -= count * ty
                moves += count
            } else {
                if (tx - sx) % ty == 0 {
                    moves += (tx - sx) / ty
                    return moves
                } else {
                    return -1
                }
            }
        } else { // ty > tx
            if tx > sx {
                count := (ty - sy) / tx
                if count == 0 {
                    count = 1
                }
                ty -= count * tx
                moves += count
            } else {
                if (ty - sy) % tx == 0 {
                    moves += (ty - sy) / tx
                    return moves
                } else {
                    return -1
                }
            }
        }
    }
    if sx == tx && sy == ty {
        return 0
    }

    if sx > tx || sy > ty {
        return -1
    }

    moves := 0

    for tx > sx || ty > sy {
        if tx == ty {
            break
        }

        if tx > ty {
            if ty == sy {
                if (tx-sx)%ty != 0 {
                    return -1
                }
                return moves + (tx-sx)/ty
            }

            if tx >= 2*ty {
                if tx%2 != 0 {
                    return -1
                }
                tx /= 2
            } else {
                tx -= ty
            }
            moves++
        } else {
            if sx == tx {
                if (ty-sy)%tx != 0 {
                    return -1
                }
                return moves + (ty-sy)/tx
            }

            if ty >= 2*tx {
                if ty%2 != 0 {
                    return -1
                }
                ty /= 2
            } else {
                ty -= tx
            }
            moves++
        }
    }

    if tx == sx && ty == sy {
        return moves
    }

    if tx == sx {
        if ty < sy || (ty-sy)%tx != 0 {
            return -1
        }
        return moves + (ty-sy)/tx
    }

    if ty == sy {
        if tx < sx || (tx-sx)%ty != 0 {
            return -1
        }
        return moves + (tx-sx)/ty
    }

    return -1
}

The Go version mirrors the Python logic. Integer division ensures correct multiple subtraction counts, and careful checks handle edge cases when one coordinate matches the starting point.

Worked Examples

Example 1: (sx, sy) = (1, 2), (tx, ty) = (5, 4)

Step	tx	ty	Moves	Explanation
0	5	4	0	Start
1	1	4	1	tx > ty, subtract ty from tx
2	1	4	2	ty > tx, subtract tx from ty
Done	1	2	2	Reached start

Example 2: (sx, sy) = (0, 1), (tx, ty) = (2, 3)

Step	tx	ty	Moves	Explanation
0	2	3	0	Start
1	2	1	1	ty > tx, subtract tx from ty
2	1	1	2	tx > ty, subtract ty from tx
3	0	1	3	ty > tx, subtract tx from ty
Done	0	1	3	Reached start

Example 3: (sx, sy) = (1, 1), (tx, ty) = (2, 2)

Here, tx == ty initially, so return -1. The Go implementation mirrors the Python logic exactly. The main differences are syntactic: integer division is implicit for ints, and there is no need for explicit type handling for modular arithmetic beyond standard operators.

Worked Examples

Example 1: sx = 1, sy = 2, tx = 5, ty = 4

We start from (5, 4).

Step	State (tx, ty)	Action	Moves
1	(5, 4)	tx > ty, tx < 2*ty so tx -= ty → (1, 4)	1
2	(1, 4)	ty > tx, reduce y by x → (1, 2)	2

We reach (1, 2) in 2 moves, so the answer is 2.

Example 2: sx = 0, sy = 1, tx = 2, ty = 3

Start from (2, 3).

Step	State	Action	Moves
1	(2, 3)	ty > tx, ty < 2*tx so ty -= tx → (2, 1)	1
2	(2, 1)	tx > ty, tx >= 2*ty so halve or adjust → (1, 1)	2
3	(1, 1)	finalize reduction to (0, 1)	3

We reach (0, 1) in 3 moves.

Example 3: sx = 1, sy = 1, tx = 2, ty = 2

We start from (2, 2). Since both coordinates are equal and cannot be uniquely reduced without ambiguity in reverse, no valid sequence can reliably reach (1, 1) under the constraints, so the algorithm returns -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(max(tx, ty)))	Each subtraction reduces the larger coordinate by at least the smaller coordinate, similar to Euclidean GCD
Space	O(1)	Only counters and variables for coordinates are stored; no additional data structures needed

The logarithmic time ensures the algorithm handles the maximum constraint values efficiently. | Time | O(log max(tx, ty)) | Each step reduces one coordinate significantly via subtraction or halving | | Space | O(1) | Only constant variables are used |

The logarithmic behavior comes from the fact that at each step we either halve a coordinate or reduce it by a substantial amount relative to the other coordinate, rapidly shrinking the problem size.

Test Cases

# Provided examples
assert Solution().minMoves(1, 2, 5, 4) == 2  # Example 1
assert Solution().minMoves(0, 1, 2, 3) == 3  # Example 2
assert Solution().minMoves(1, 1, 2, 2) == -1  # Example 3

# Boundary cases
assert Solution().minMoves(0, 0, 0, 0) == 0  # Start equals target
assert Solution().minMoves(0, 0, 1,

assert Solution().minMoves(1, 2, 5, 4) == 2 # basic example assert Solution().minMoves(0, 1, 2, 3) == 3 # linear growth case assert Solution().minMoves(1, 1, 2, 2) == -1 # impossible symmetric case assert Solution().minMoves(0, 0, 0, 0) == 0 # already at target assert Solution().minMoves(1, 1, 1, 10) == 1 # single-axis growth assert Solution().minMoves(2, 3, 2, 100) == 97 # pure vertical accumulation assert Solution().minMoves(3, 2, 100, 2) == 97 # pure horizontal accumulation

| Test | Why |
| --- | --- |
| identical start and end | verifies zero-move base case |
| sample inputs | validates correctness on canonical cases |
| single-axis growth | ensures linear accumulation is handled |
| large skewed growth | stress tests repeated subtraction logic |

## Edge Cases

One important edge case occurs when the starting point is already equal to the target. In this situation, no moves are required, and the algorithm must immediately return zero without entering any loops.

Another subtle case arises when one coordinate is already equal to its target value early in the reverse process. In this scenario, the remaining coordinate must be checked for divisibility by the fixed coordinate, because all remaining forward moves would have repeatedly added a constant value. Failing to enforce this divisibility condition can lead to incorrect acceptance of unreachable states.

A third edge case involves symmetric states where `x == y`. In such cases, the reverse operation becomes ambiguous because both subtraction and halving may appear valid. Without careful handling, this can lead to incorrect branching or infinite loops. The implementation handles this by breaking symmetry early and enforcing strict reduction rules, ensuring deterministic progress toward the start state.