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.
Example 1:
Input: xCorner = 3, yCorner = 4, circles = [[2,1,1]]
Output: true
Explanation:
The black curve shows a possible path between (0, 0) and (3, 4).
Example 2:
Input: xCorner = 3, yCorner = 3, circles = [[1,1,2]]
Output: false
Explanation:
No path exists from (0, 0) to (3, 3).
Example 3:
Input: xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]
Output: false
Explanation:
No path exists from (0, 0) to (3, 3).
Example 4:
Input: xCorner = 4, yCorner = 4, circles = [[5,5,1]]
Output: true
Explanation:
Constraints:
3 <= xCorner, yCorner <= 1091 <= circles.length <= 1000circles[i].length == 31 <= xi, yi, ri <= 109Problem Overview: You are given a rectangle and several circular obstacles. The task is to determine whether you can move from the bottom-left corner to the top-right corner without entering any circle. Movement is allowed inside the rectangle, but touching or crossing a circle blocks the path.
Approach 1: Grid-Based BFS Traversal (Time: O(W × H), Space: O(W × H))
This approach converts the rectangle into a grid and performs a Breadth-First Search. Each grid cell represents a coordinate in the rectangle. First mark all cells that fall inside any circle using a distance check: (x - cx)^2 + (y - cy)^2 ≤ r^2. These cells become blocked. Then start BFS from (0,0), exploring valid neighbors while avoiding blocked cells and staying inside bounds. If BFS reaches the top-right corner, the path exists.
The key idea is modeling the geometry problem as a graph traversal problem. BFS guarantees that all reachable cells are explored systematically. This approach is easy to implement and intuitive when thinking in terms of reachable states, but it becomes expensive when the rectangle dimensions are large.
Approach 2: Mathematical Distance + Union-Find (Time: O(n²), Space: O(n))
The optimized approach avoids scanning the entire grid. Instead, treat each circle as a node and detect whether circles connect to form a continuous barrier that blocks the path. Two circles are connected if the distance between their centers is less than or equal to the sum of their radii. Use Union Find (Disjoint Set Union) to group overlapping circles.
Next check whether any connected component touches both sides of the rectangle in a way that forms a wall (for example, connecting the left and right edges or top and bottom edges, depending on constraints). If such a barrier exists, it prevents reaching the opposite corner. Distance checks and boundary intersection tests rely on simple geometry formulas. This method scales well because it only processes circle relationships rather than every grid point.
Recommended for interviews: Start by explaining the grid BFS approach because it clearly models the reachable-area idea. Then move to the mathematical union-find strategy. Interviewers usually expect the optimized geometric reasoning since it reduces the search space dramatically and demonstrates strong problem-solving with geometry and graph connectivity.
This approach involves treating the rectangle as a grid and using a Breadth-First Search (BFS) algorithm to find a path from the bottom left to the top right corner. The key challenge is marking areas that are obstructed by circles as inaccessible. For high efficiency, we ensure that only necessary points inside the rectangle are checked and circular areas are systematically marked as blocked by checking their distance to any circle's center.
This C program treats the grid within the rectangle as explored through BFS. It checks if points are inside any circle using Euclidean distance, blocking those that are.
Time Complexity: O(xCorner * yCorner * circlesSize), Space Complexity: O(xCorner * yCorner)
This approach calculates distances mathematically to determine if traversal from the start to the end is possible by potentially taking straight paths while checking if these intersect with any circles. By leveraging geometric properties directly, one can avoid unnecessary grid computation and reduce complexity through direct distance evaluations and thorough conditional logic.
A C solution using Euclidean distance between points, checking if any circle center within the rectangle obstructs start-to-end pathways directly by examining radial intersections.
Time Complexity: O(circlesSize), Space Complexity: O(1)
According to the problem description, we discuss the following cases:
When there is only one circle in circles:
(0, 0) is inside the circle (including the boundary), or the ending point (xCorner, yCorner) is inside the circle, then it is impossible to satisfy the condition of "not touching the circle".When there are multiple circles in circles:
Based on the above analysis, we traverse all circles. For the current circle, if the starting point or ending point is inside the circle, we directly return false. Otherwise, if this point has not been visited and the circle intersects with the left or top side of the rectangle, we start a depth-first search (DFS) from this circle. During the search, if we find a circle that intersects with the right or bottom side of the rectangle, it means the obstacle area formed by the circles blocks the path from the bottom-left corner to the top-right corner of the rectangle, and we return false.
We define dfs(i) to represent starting a DFS from the i-th circle. If we find a circle that intersects with the right or bottom side of the rectangle, we return true; otherwise, we return false.
The execution process of the function dfs(i) is as follows:
true;j has not been visited, and circle i intersects with circle j, and one of the intersection points of these two circles is inside the rectangle, continue the DFS from circle j. If we find a circle that intersects with the right or bottom side of the rectangle, return true;false.In the above process, we need to determine whether two circles O_1 = (x_1, y_1, r_1) and O_2 = (x_2, y_2, r_2) intersect. If the distance between the centers of the two circles does not exceed the sum of their radii, i.e., (x_1 - x_2)^2 + (y_1 - y_2)^2 \le (r_1 + r_2)^2, then they intersect.
We also need to find an intersection point of the two circles. We take a point A = (x, y) such that \frac{O_1 A}{O_1 O_2} = \frac{r_1}{r_1 + r_2}. If the two circles intersect, point A must be in the intersection. In this case, \frac{x - x_1}{x_2 - x_1} = \frac{r_1}{r_1 + r_2}, solving for x = \frac{x_1 r_2 + x_2 r_1}{r_1 + r_2}. Similarly, y = \frac{y_1 r_2 + y_2 r_1}{r_1 + r_2}. As long as this point is inside the rectangle, we can continue the DFS, satisfying:
$
\begin{cases}
x_1 r_2 + x_2 r_1 < (r_1 + r_2) times xCorner \
y_1 r_2 + y_2 r_1 < (r_1 + r_2) times yCorner
\end{cases}
The time complexity is O(n^2), and the space complexity is O(n). Here, n$ is the number of circles.
| Approach | Complexity |
|---|---|
| Grid-Based BFS Approach | Time Complexity: O(xCorner * yCorner * circlesSize), Space Complexity: O(xCorner * yCorner) |
| Mathematical Distance Calculations | Time Complexity: O(circlesSize), Space Complexity: O(1) |
| DFS + Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Grid-Based BFS Traversal | O(W × H) | O(W × H) | Useful for small rectangle sizes or when modeling the problem as a reachable grid is easier to reason about. |
| Mathematical Distance + Union-Find | O(n²) | O(n) | Best for large coordinate ranges where scanning the entire grid is infeasible. Focuses only on circle interactions. |
A-D | Leetcode Weekly Contest 408 Editorials | Check if the Rectangle Corner Is Reachable | Solution • Abhinav Awasthi • 6,984 views views
Watch 4 more video solutions →Practice Check if the Rectangle Corner Is Reachable with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor