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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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) |
Stop solving 500+ Leetcode problems • Sahil & Sarra • 512,544 views views
Watch 9 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