Check if the Rectangle Corner Is Reachable

Problem Description

You are given two positive integers xCorner and yCorner, and a 2D array circles, where circles[i] = [x_i, y_i, r_i] denotes a circle with center at (x_i, y_i) and radius r_i. 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.

Key Insights

• The path must lie entirely within the rectangle defined by (0, 0) to (xCorner, yCorner).
• The path cannot intersect or touch any of the circles defined by their center coordinates and radius.
• The problem can be visualized as a graph or grid traversal problem, with obstacles (circles) to avoid.
• A breadth-first search (BFS) or depth-first search (DFS) could be employed to explore possible paths.
• The circles can be checked for intersection with the path using the distance formula.

Space and Time Complexity

Time Complexity: O(n) where n is the number of circles, as each circle needs to be checked for intersection with the path. Space Complexity: O(1) since we are using a constant amount of space for calculations and do not require additional data structures based on input size.

Solution

The solution involves checking if there exists a clear path from (0, 0) to (xCorner, yCorner) while avoiding circles. We can achieve this by calculating the distance from the path to the edges of the circles.

1. For each circle, compute the distance from the closest point on the rectangle edge to the circle center.
2. If this distance is less than the radius of the circle, the path is obstructed.
3. If all circles are checked and none obstruct the path, return true; otherwise, return false.

Code Solutions