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)
| 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) |
| 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