Watch 5 video solutions for Check if the Rectangle Corner Is Reachable, a hard level problem involving Array, Math, Depth-First Search. This walkthrough by Abhinav Awasthi has 6,984 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |