Check if the rectangle corner is reachable

Array Math Depth-First Search Breadth-First Search Union-Find Geometry

25.3% acceptance

Feb 25, 2026

121

You are given two positive integers xCorner and yCorner, and a 2D array circles, where circles[i] = [xi, yi, ri] denotes a circle with center at (xi, yi) and radius ri. There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate (xCorner, yCorner). You need to check whether there is a path from the bottom left corner to the top right corner such that the entire path lies inside the rectangle, does not touch or lie inside any circle, and touches the rectangle only at the two corners. Return true if such a path exists, and false otherwise.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/// Returns true if the lens (overlap region) of two circles intersects the closed rectangle
/// [0, xc] × [0, yc].  Assumes the circles already overlap (d ≤ r1+r2).
fn lens_intersects_rect(
  cx1: i64, cy1: i64, r1: i64,
  cx2: i64, cy2: i64, r2: i64,
  xc: i64, yc: i64,
) -> bool {
  let xc_f = xc as f64;
  let yc_f = yc as f64;
  let cx1f = cx1 as f64; let cy1f = cy1 as f64; let r1f = r1 as f64;
  let cx2f = cx2 as f64; let cy2f = cy2 as f64; let r2f = r2 as f64;

  // ── 1. Rectangle corners inside both circles (exact integer) ──────────────
  let in_both_i = |px: i64, py: i64| -> bool {
    (px-cx1)*(px-cx1) + (py-cy1)*(py-cy1) <= r1*r1
      && (px-cx2)*(px-cx2) + (py-cy2)*(py-cy2) <= r2*r2
  };
  for &(px, py) in &[(0i64,0i64),(xc,0),(0,yc),(xc,yc)] {
    if in_both_i(px, py) { return true; }
  }

  let in_rect  = |px: f64, py: f64| px >= 0.0 && px <= xc_f && py >= 0.0 && py <= yc_f;
  let in_disk  = |px: f64, py: f64, ccx: f64, ccy: f64, rr: f64| {
    (px-ccx)*(px-ccx) + (py-ccy)*(py-ccy) <= rr*rr
  };

  // ── 2. Circle-circle intersection points inside the rectangle ─────────────
  let dx = cx2f - cx1f;
  let dy = cy2f - cy1f;
  let d2 = dx*dx + dy*dy;
  let d  = d2.sqrt();
  if d > 0.0 {
    let a  = (r1f*r1f - r2f*r2f + d2) / (2.0 * d);
    let h2 = r1f*r1f - a*a;
    if h2 >= 0.0 {
      let h  = h2.sqrt();
      let mx = cx1f + a * dx / d;
      let my = cy1f + a * dy / d;
      let p1x = mx + h * dy / d;  let p1y = my - h * dx / d;
      let p2x = mx - h * dy / d;  let p2y = my + h * dx / d;
      if in_rect(p1x, p1y) || in_rect(p2x, p2y) { return true; }
    }
  }

  // ── 3. Points where each circle crosses a rectangle edge, checked vs the
  //        other circle ────────────────────────────────────────────────────
  // Returns true if any arc-edge intersection point of (ccx,ccy,rr) that lies
  // on the rectangle boundary is also inside (ocx,ocy,orr).
  let check = |ccx: f64, ccy: f64, rr: f64, ocx: f64, ocy: f64, orr: f64| -> bool {
    // bottom edge y = 0
    let disc = rr*rr - ccy*ccy;
    if disc >= 0.0 {
      let sq = disc.sqrt();
      for &px in &[ccx+sq, ccx-sq] {
        if in_rect(px, 0.0) && in_disk(px, 0.0, ocx, ocy, orr) { return true; }
      }
    }
    // top edge y = yc_f
    let disc = rr*rr - (ccy - yc_f)*(ccy - yc_f);
    if disc >= 0.0 {
      let sq = disc.sqrt();
      for &px in &[ccx+sq, ccx-sq] {
        if in_rect(px, yc_f) && in_disk(px, yc_f, ocx, ocy, orr) { return true; }
      }
    }
    // left edge x = 0
    let disc = rr*rr - ccx*ccx;
    if disc >= 0.0 {
      let sq = disc.sqrt();
      for &py in &[ccy+sq, ccy-sq] {
        if in_rect(0.0, py) && in_disk(0.0, py, ocx, ocy, orr) { return true; }
      }
    }
    // right edge x = xc_f
    let disc = rr*rr - (ccx - xc_f)*(ccx - xc_f);
    if disc >= 0.0 {
      let sq = disc.sqrt();
      for &py in &[ccy+sq, ccy-sq] {
        if in_rect(xc_f, py) && in_disk(xc_f, py, ocx, ocy, orr) { return true; }
      }
    }
    false
  };

  check(cx1f, cy1f, r1f, cx2f, cy2f, r2f) || check(cx2f, cy2f, r2f, cx1f, cy1f, r1f)
}

impl Solution {
  pub fn can_reach_corner(x_corner: i32, y_corner: i32, circles: Vec<Vec<i32>>) -> bool {
    let n = circles.len();
    let xc = x_corner as i64;
    let yc = y_corner as i64;

    // Union-Find
    let mut parent: Vec<usize> = (0..n + 2).collect();
    let bl = n;     // virtual "bottom+left boundary" group
    let tr = n + 1; // virtual "top+right boundary" group

    let find = |parent: &mut Vec<usize>, mut x: usize| -> usize {
      while parent[x] != x {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
      }
      x
    };

    // touches_tl: circle crosses LEFT edge (x=0, 0<=y<=yc) OR TOP edge (y=yc, 0<=x<=xc)
    let touches_tl = |cx: i64, cy: i64, r: i64| -> bool {
      (cx <= r && 0 <= cy && cy <= yc) ||
      (cy + r >= yc && 0 <= cx && cx <= xc)
    };

    // touches_br: circle crosses BOTTOM edge (y=0, 0<=x<=xc) OR RIGHT edge (x=xc, 0<=y<=yc)
    let touches_br = |cx: i64, cy: i64, r: i64| -> bool {
      (cy <= r && 0 <= cx && cx <= xc) ||
      (cx + r >= xc && 0 <= cy && cy <= yc)
    };

    // Circle's interior strictly intersects the closed rectangle [0,xc]x[0,yc]
    let intersects_rect = |cx: i64, cy: i64, r: i64| -> bool {
      let nx = cx.clamp(0, xc);
      let ny = cy.clamp(0, yc);
      (cx - nx) * (cx - nx) + (cy - ny) * (cy - ny) < r * r
    };

    // First: check if any circle covers start (0,0) or end (xc,yc)
    for i in 0..n {
      let cx = circles[i][0] as i64;
      let cy = circles[i][1] as i64;
      let r  = circles[i][2] as i64;
      if cx * cx + cy * cy <= r * r { return false; }
      if (xc - cx) * (xc - cx) + (yc - cy) * (yc - cy) <= r * r { return false; }
    }

    // Union overlapping circles — only if both intersect the rectangle interior
    // AND their lens (overlap region) also intersects the rectangle.
    for i in 0..n {
      let cxi = circles[i][0] as i64;
      let cyi = circles[i][1] as i64;
      let ri  = circles[i][2] as i64;
      if !intersects_rect(cxi, cyi, ri) { continue; }
      for j in i + 1..n {
        let cxj = circles[j][0] as i64;
        let cyj = circles[j][1] as i64;
        let rj  = circles[j][2] as i64;
        if !intersects_rect(cxj, cyj, rj) { continue; }
        let dx = cxi - cxj;
        let dy = cyi - cyj;
        let dr = ri + rj;
        if dx * dx + dy * dy <= dr * dr {
          // Extra check: lens must actually intersect the rectangle
          if !lens_intersects_rect(cxi, cyi, ri, cxj, cyj, rj, xc, yc) { continue; }
          let pi = find(&mut parent, i);
          let pj = find(&mut parent, j);
          if pi != pj { parent[pi] = pj; }
        }
      }
    }

    // Then connect circles to boundary virtual nodes
    for i in 0..n {
      let cx = circles[i][0] as i64;
      let cy = circles[i][1] as i64;
      let r  = circles[i][2] as i64;

      if touches_tl(cx, cy, r) {
        let pi = find(&mut parent, i);
        let pb = find(&mut parent, bl);
        if pi != pb { parent[pi] = pb; }
      }
      if touches_br(cx, cy, r) {
        let pi = find(&mut parent, i);
        let pt = find(&mut parent, tr);
        if pi != pt { parent[pi] = pt; }
      }
    }

    find(&mut parent, bl) != find(&mut parent, tr)
  }
}