Check if the Rectangle Corner Is Reachable

Check if the Rectangle Corner Is Reachable

What is this problem about?

This "Hard" geometry problem asks if a point can move from $(0, 0)$ to $(X, Y)$ within a rectangle without touching or crossing any of a set of given circles. The movement is restricted to the interior of the rectangle $[0, X] imes [0, Y]$. This problem combines pathfinding with geometric intersection checks.

Why is this asked in interviews?

Uber and Amazon ask this to test a candidate's ability to model a continuous geometric problem as a discrete graph problem. The key insight is that the destination is unreachable if the circles form a "chain" or "barrier" that connects the boundaries of the rectangle in a way that blocks the path. It tests skills in Geometry and Graph Connectivity.

Algorithmic pattern used

The primary pattern is Union Find or BFS/DFS on a graph. You treat each circle as a node and the boundaries of the rectangle (Top, Bottom, Left, Right) as special nodes. Two circles are connected if they intersect or touch. A circle is connected to a boundary if it intersects or touches that boundary. The path from $(0, 0)$ to $(X, Y)$ is blocked if there is a path from the (Top or Right) boundary to the (Bottom or Left) boundary.

Example explanation

Imagine a rectangle $10 imes 10$.

• Circle 1 is at $(5, 5)$ with radius 6.
• This circle touches both the Left boundary ($5-6 < 0$) and the Top boundary ($5+6 > 10$).
• It also touches the Bottom boundary and the Right boundary.
• Since it connects the Top/Right boundary to the Bottom/Left boundary, it forms a complete barrier. Result: False.

Common mistakes candidates make

The most common mistake is trying to use a grid-based BFS, which is inaccurate for continuous coordinates. Another error is incorrectly calculating the distance between circles (forgetting to use the squared distance to avoid floating-point issues). Many candidates also struggle with identifying which specific boundary connections actually block the path.

Interview preparation tip

In geometry problems, always look for the "dual" problem. Instead of asking "Can I find a path?", ask "Is there a barrier?". Barriers are often easier to identify using connectivity algorithms like Union Find.