Minimum moves to reach target in grid

Math

14.9% acceptance

Feb 25, 2026

You are given four integers sx, sy, tx, and ty, representing two points (sx, sy) and (tx, ty) on an infinitely large 2D grid. You start at (sx, sy). At any point (x, y), define m = max(x, y). You can either: Move to (x + m, y), or Move to (x, y + m). Return the minimum number of moves required to reach (tx, ty). If it is impossible to reach the target, return -1.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_moves(sx: i32, sy: i32, tx: i32, ty: i32) -> i32 {
    let (sx, sy) = (sx as i64, sy as i64);
    let (mut tx, mut ty) = (tx as i64, ty as i64);
    let mut moves = 0i32;
    loop {
      if tx == sx && ty == sy { return moves; }
      if tx < sx || ty < sy { return -1; }
      if tx == ty {
        // Predecessors are (tx, 0) [from doubling y] or (0, ty) [from doubling x].
        // Pick based on which coordinate needs to reach zero.
        if tx == 0 { return -1; }
        if sy == 0 {
          ty = 0; // predecessor is (tx, 0)
        } else if sx == 0 {
          tx = 0; // predecessor is (0, ty)
        } else {
          return -1; // unreachable when both sx > 0 and sy > 0
        }
        moves += 1;
      } else if tx > ty {
        if tx < 2 * ty {
          // unique predecessor: (tx - ty, ty)
          tx -= ty;
          moves += 1;
        } else {
          // predecessor: (tx/2, ty), must have even tx
          if tx % 2 != 0 { return -1; }
          tx /= 2;
          moves += 1;
        }
      } else {
        // ty > tx
        if tx == 0 {
          // Can only halve ty
          if ty % 2 != 0 { return -1; }
          ty /= 2;
          moves += 1;
        } else if ty < 2 * tx {
          // unique predecessor: (tx, ty - tx)
          ty -= tx;
          moves += 1;
        } else {
          // predecessor: (tx, ty/2), must have even ty
          if ty % 2 != 0 { return -1; }
          ty /= 2;
          moves += 1;
        }
      }
    }
  }
}