Check if the Rectangle Corner Is Reachable solution and explanation
Google
4 more videos on this problem
A-D | Leetcode Weekly Contest 408 Editorials | Check if the Rectangle Corner Is Reachable | SolutionAbhinav Awasthi · 53:28 · 7K views
3235. Check if the Rectangle Corner Is Reachable | Weekly Leetcode 408codingMohan · 20:49 · 1K views
Q4. Check if the Rectangle Corner Is Reachable Solution | LEETCODE WEEKLY CONTEST 408 SOLUTIONJUST CODE · 1:59 · 870 views
3235. Check if the Rectangle Corner Is Reachable (Leetcode Hard)Programming Live with Larry · 37:55 · 657 views
3235. Check if the Rectangle Corner Is Reachable (leetcode hard)Coder on A Farm · 18:47 · 237 views
The problem
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 <= 109
Approach overview
Problem 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 1: Grid-Based BFS Approach
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.
from collections import deque
class Solution:
def isWithinCircle(self, x, y, cx, cy, cr):
return (x - cx) ** 2 + (y - cy) ** 2 <= cr ** 2
def bfs(self, xCorner, yCorner, circles):
visited = [[False] * (yCorner + 1) for _ in range(xCorner + 1)]
queue = deque([(0, 0)])
visited[0][0] = True
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
x, y = queue.popleft()
if x == xCorner and y == yCorner:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx <= xCorner and 0 <= ny <= yCorner and not visited[nx][ny]:
in_circle = any(self.isWithinCircle(nx, ny, cx, cy, cr) for cx, cy, cr in circles)
if not in_circle:
visited[nx][ny] = True
queue.append((nx, ny))
return False
solution = Solution()
circles = [[2, 1, 1]] # First test case
xCorner = 3
yCorner = 4
print(solution.bfs(xCorner, yCorner, circles))import java.util.*;
public class Main {
public static boolean isWithinCircle(int x, int y, int cx, int cy, int cr) {
return Math.pow(x - cx, 2) + Math.pow(y - cy, 2) <= Math.pow(cr, 2);
}
public static boolean bfs(int xCorner, int yCorner, int[][] circles) {
boolean[][] visited = new boolean[xCorner + 1][yCorner + 1];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited[0][0] = true;
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
if (x == xCorner && y == yCorner) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= xCorner && ny <= yCorner && !visited[nx][ny]) {
boolean inCircle = false;
for (int[] circle : circles) {
if (isWithinCircle(nx, ny, circle[0], circle[1], circle[2])) {
inCircle = true;
break;
}
}
if (!inCircle) {
queue.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
return false;
}
public static void main(String[] args) {
int[][] circles = {{2, 1, 1}};
int xCorner = 3, yCorner = 4;
if (bfs(xCorner, yCorner, circles))
System.out.println("true");
else
System.out.println("false");
}
}#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
bool isWithinCircle(int x, int y, int cx, int cy, int cr) {
return pow(x - cx, 2) + pow(y - cy, 2) <= pow(cr, 2);
}
bool bfs(int xCorner, int yCorner, vector<vector<int>>& circles) {
vector<vector<bool>> visited(xCorner + 1, vector<bool>(yCorner + 1, false));
queue<pii> q;
q.push({0, 0});
visited[0][0] = true;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while (!q.empty()) {
int x, y;
tie(x, y) = q.front();
q.pop();
if (x == xCorner && y == yCorner)
return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= xCorner && ny <= yCorner && !visited[nx][ny]) {
bool inCircle = false;
for (auto& circle : circles) {
if (isWithinCircle(nx, ny, circle[0], circle[1], circle[2])) {
inCircle = true;
break;
}
}
if (!inCircle) {
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
}
return false;
}
int main() {
vector<vector<int>> circles = {{2, 1, 1}};
int xCorner = 3, yCorner = 4;
if (bfs(xCorner, yCorner, circles))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}function isWithinCircle(x, y, cx, cy, cr) {
return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= cr * cr;
}
function bfs(xCorner, yCorner, circles) {
let visited = Array.from({ length: xCorner + 1 }, () => Array(yCorner + 1).fill(false));
let queue = [[0, 0]];
visited[0][0] = true;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0) {
let [x, y] = queue.shift();
if (x === xCorner && y === yCorner) return true;
for (let [dx, dy] of directions) {
let nx = x + dx, ny = y + dy;
if (nx >= 0 && ny >= 0 && nx <= xCorner && ny <= yCorner && !visited[nx][ny]) {
let inCircle = circles.some(([cx, cy, cr]) => isWithinCircle(nx, ny, cx, cy, cr));
if (!inCircle) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
return false;
}
const circles = [[2, 1, 1]];
const xCorner = 3,
yCorner = 4;
console.log(bfs(xCorner, yCorner, circles));#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#define MAX 1500
bool isWithinCircle(int x, int y, int cx, int cy, int cr) {
return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= cr * cr;
}
bool bfs(int xCorner, int yCorner, int circles[][3], int circlesSize) {
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool visited[MAX][MAX];
memset(visited, false, sizeof(visited));
if (isWithinCircle(0, 0, circles[0][0], circles[0][1], circles[0][2]))
return false;
visited[0][0] = true;
int queue[MAX * MAX][2];
int front = 0, rear = 0;
queue[rear][0] = 0;
queue[rear++][1] = 0;
while (front < rear) {
int x = queue[front][0];
int y = queue[front++][1];
if (x == xCorner && y == yCorner)
return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx <= xCorner && ny >= 0 && ny <= yCorner && !visited[nx][ny]) {
bool inCircle = false;
for (int j = 0; j < circlesSize; j++) {
if (isWithinCircle(nx, ny, circles[j][0], circles[j][1], circles[j][2])) {
inCircle = true;
break;
}
}
if (!inCircle) {
visited[nx][ny] = true;
queue[rear][0] = nx;
queue[rear++][1] = ny;
}
}
}
}
return false;
}
int main() {
int circles[1][3] = {{2, 1, 1}}; // First test case
int xCorner = 3, yCorner = 4;
if (bfs(xCorner, yCorner, circles, 1))
printf("true\n");
else
printf("false\n");
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static bool IsWithinCircle(int x, int y, int cx, int cy, int cr) {
return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= cr * cr;
}
public static bool Bfs(int xCorner, int yCorner, int[][] circles) {
bool[,] visited = new bool[xCorner + 1, yCorner + 1];
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((0, 0));
visited[0, 0] = true;
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
while (queue.Count > 0) {
var (x, y) = queue.Dequeue();
if (x == xCorner && y == yCorner) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= xCorner && ny <= yCorner && !visited[nx, ny]) {
bool inCircle = false;
foreach (var circle in circles) {
if (IsWithinCircle(nx, ny, circle[0], circle[1], circle[2])) {
inCircle = true;
break;
}
}
if (!inCircle) {
queue.Enqueue((nx, ny));
visited[nx, ny] = true;
}
}
}
}
return false;
}
public static void Main(string[] args) {
int[][] circles = new int[][] { new int[] {2, 1, 1} };
int xCorner = 3, yCorner = 4;
Console.WriteLine(Bfs(xCorner, yCorner, circles) ? "true" : "false");
}
}Utilizing Python's deque, each potential path step is checked for any obstructions by circles. This example illustrates a grid exploration using BFS, identifying permissible moves on each iteration.
Time Complexity: O(xCorner * yCorner * circlesSize), Space Complexity: O(xCorner * yCorner)
Approach 2: Mathematical Distance Calculations
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.
class Solution:
def canPassWithoutIntersection(self, xCorner, yCorner, circles):
for x, y, r in circles:
if 0 <= x <= xCorner and 0 <= y <= yCorner:
d1 = (x**2 + y**2)**0.5
d2 = ((xCorner-x)**2 + (yCorner-y)**2)**0.5
if d1 <= r or d2 <= r:
return False
return True
solution = Solution()
circles = [[2, 1, 1]]
xCorner, yCorner = 3, 4
print(solution.canPassWithoutIntersection(xCorner, yCorner, circles))public class Main {
public static boolean canPassWithoutIntersection(int xCorner, int yCorner, int[][] circles) {
for (int[] circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
if (x >= 0 && x <= xCorner && y >= 0 && y <= yCorner) {
double d1 = Math.sqrt(x*x + y*y);
double d2 = Math.sqrt((xCorner-x)*(xCorner-x) + (yCorner-y)*(yCorner-y));
if (d1 <= r || d2 <= r) return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] circles = {{2, 1, 1}};
int xCorner = 3, yCorner = 4;
if (canPassWithoutIntersection(xCorner, yCorner, circles))
System.out.println("true");
else
System.out.println("false");
}
}#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
bool canPassWithoutIntersection(int xCorner, int yCorner, vector<vector<int>>& circles) {
for (const auto& circle : circles) {
int x = circle[0], y = circle[1], r = circle[2];
if (x >= 0 && x <= xCorner && y >= 0 && y <= yCorner) {
double d1 = sqrt(x*x + y*y);
double d2 = sqrt((xCorner-x)*(xCorner-x) + (yCorner-y)*(yCorner-y));
if (d1 <= r || d2 <= r) return false;
}
}
return true;
}
int main() {
vector<vector<int>> circles = {{2, 1, 1}};
int xCorner = 3, yCorner = 4;
if (canPassWithoutIntersection(xCorner, yCorner, circles))
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}function canPassWithoutIntersection(xCorner, yCorner, circles) {
for (let [cx, cy, cr] of circles) {
if (cx >= 0 && cy >= 0 && cx <= xCorner && cy <= yCorner) {
const d1 = Math.sqrt(cx * cx + cy * cy);
const d2 = Math.sqrt((xCorner - cx) ** 2 + (yCorner - cy) ** 2);
if (d1 <= cr || d2 <= cr) return false;
}
}
return true;
}
const circles = [[2, 1, 1]];
const xCorner = 3, yCorner = 4;
console.log(canPassWithoutIntersection(xCorner, yCorner, circles));#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool canPassWithoutIntersection(int xCorner, int yCorner, int circles[][3], int circlesSize) {
for (int i = 0; i < circlesSize; i++){
int x = circles[i][0], y = circles[i][1], r = circles[i][2];
if (x >= 0 && x <= xCorner && y >= 0 && y <= yCorner) {
double d1 = sqrt(x*x + y*y);
double d2 = sqrt((xCorner-x)*(xCorner-x) + (yCorner-y)*(yCorner-y));
if (d1 <= r || d2 <= r)
return false;
}
}
return true;
}
int main() {
int circles[1][3] = {{2, 1, 1}};
int xCorner = 3, yCorner = 4;
if (canPassWithoutIntersection(xCorner, yCorner, circles, 1))
printf("true\n");
else
printf("false\n");
return 0;
}using System;
public class Solution {
public static bool CanPassWithoutIntersection(int xCorner, int yCorner, int[][] circles) {
foreach (var circle in circles) {
int x = circle[0], y = circle[1], r = circle[2];
if (x >= 0 && x <= xCorner && y >= 0 && y <= yCorner) {
double d1 = Math.Sqrt(x*x + y*y);
double d2 = Math.Sqrt(Math.Pow(xCorner-x, 2) + Math.Pow(yCorner-y, 2));
if (d1 <= r || d2 <= r) return false;
}
}
return true;
}
public static void Main(string[] args) {
int[][] circles = new int[][] { new int[] {2, 1, 1} };
int xCorner = 3, yCorner = 4;
Console.WriteLine(CanPassWithoutIntersection(xCorner, yCorner, circles) ? "true" : "false");
}
}In Python, this solution strategically examines possible non-interfered lines, using direct circle evaluations to determine if corner points can be traversed uneventfully.
Time Complexity: O(circlesSize), Space Complexity: O(1)
Approach 3: DFS + Mathematics
According to the problem description, we discuss the following cases:
When there is only one circle in circles:
- If the starting point
(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". - If the circle intersects with the left or top side of the rectangle and also intersects with the right or bottom side of the rectangle, then the circle will block the path from the bottom-left corner to the top-right corner of the rectangle, making it impossible to satisfy the condition of "not touching the circle".
When there are multiple circles in circles:
- Similar to the above case, if the starting point or ending point is inside a circle, it is impossible to satisfy the condition of "not touching the circle".
- If there are multiple circles, they may intersect within the rectangle, forming a larger obstacle area. As long as this obstacle area intersects with the left or top side of the rectangle and also intersects with the right or bottom side of the rectangle, it is impossible to satisfy the condition of "not touching the circle". If the intersecting area is not inside the rectangle, it cannot be merged because the intersecting area cannot block the path inside the rectangle. Additionally, if part of the intersecting area is inside the rectangle and part is outside, these circles can be used as starting or ending points and can be merged or not. We only need to choose one of the intersecting points. If this point is inside the rectangle, we can merge these 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:
- If the current circle intersects with the right or bottom side of the rectangle, return
true; - Otherwise, mark the current circle as visited;
- Next, traverse all other circles. If circle
jhas not been visited, and circleiintersects with circlej, and one of the intersection points of these two circles is inside the rectangle, continue the DFS from circlej. If we find a circle that intersects with the right or bottom side of the rectangle, returntrue; - If no such circle is found, return
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.
function canReachCorner(xCorner: number, yCorner: number, circles: number[][]): boolean {
const inCircle = (x: bigint, y: bigint, cx: bigint, cy: bigint, r: bigint): boolean => {
const dx = x - cx;
const dy = y - cy;
return dx * dx + dy * dy <= r * r;
};
const crossLeftTop = (cx: bigint, cy: bigint, r: bigint): boolean => {
const a = BigInt(Math.abs(Number(cx))) <= r && cy >= 0n && cy <= BigInt(yCorner);
const b =
BigInt(Math.abs(Number(cy - BigInt(yCorner)))) <= r &&
cx >= 0n &&
cx <= BigInt(xCorner);
return a || b;
};
const crossRightBottom = (cx: bigint, cy: bigint, r: bigint): boolean => {
const a =
BigInt(Math.abs(Number(cx - BigInt(xCorner)))) <= r &&
cy >= 0n &&
cy <= BigInt(yCorner);
const b = BigInt(Math.abs(Number(cy))) <= r && cx >= 0n && cx <= BigInt(xCorner);
return a || b;
};
const n = circles.length;
const vis: boolean[] = new Array(n).fill(false);
const dfs = (i: number): boolean => {
const [x1, y1, r1] = circles[i].map(BigInt);
if (crossRightBottom(x1, y1, r1)) {
return true;
}
vis[i] = true;
for (let j = 0; j < n; j++) {
if (vis[j]) continue;
const [x2, y2, r2] = circles[j].map(BigInt);
if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2)) {
continue;
}
if (
x1 * r2 + x2 * r1 < (r1 + r2) * BigInt(xCorner) &&
y1 * r2 + y2 * r1 < (r1 + r2) * BigInt(yCorner) &&
dfs(j)
) {
return true;
}
}
return false;
};
for (let i = 0; i < n; i++) {
const [x, y, r] = circles[i].map(BigInt);
if (inCircle(0n, 0n, x, y, r) || inCircle(BigInt(xCorner), BigInt(yCorner), x, y, r)) {
return false;
}
if (!vis[i] && crossLeftTop(x, y, r) && dfs(i)) {
return false;
}
}
return true;
}func canReachCorner(xCorner int, yCorner int, circles [][]int) bool {
inCircle := func(x, y, cx, cy, r int) bool {
dx, dy := x-cx, y-cy
return dx*dx+dy*dy <= r*r
}
crossLeftTop := func(cx, cy, r int) bool {
a := abs(cx) <= r && cy >= 0 && cy <= yCorner
b := abs(cy-yCorner) <= r && cx >= 0 && cx <= xCorner
return a || b
}
crossRightBottom := func(cx, cy, r int) bool {
a := abs(cx-xCorner) <= r && cy >= 0 && cy <= yCorner
b := abs(cy) <= r && cx >= 0 && cx <= xCorner
return a || b
}
vis := make([]bool, len(circles))
var dfs func(int) bool
dfs = func(i int) bool {
c := circles[i]
x1, y1, r1 := c[0], c[1], c[2]
if crossRightBottom(x1, y1, r1) {
return true
}
vis[i] = true
for j, c2 := range circles {
if vis[j] {
continue
}
x2, y2, r2 := c2[0], c2[1], c2[2]
if (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) > (r1+r2)*(r1+r2) {
continue
}
if x1*r2+x2*r1 < (r1+r2)*xCorner && y1*r2+y2*r1 < (r1+r2)*yCorner && dfs(j) {
return true
}
}
return false
}
for i, c := range circles {
x, y, r := c[0], c[1], c[2]
if inCircle(0, 0, x, y, r) || inCircle(xCorner, yCorner, x, y, r) {
return false
}
if !vis[i] && crossLeftTop(x, y, r) && dfs(i) {
return false
}
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn can_reach_corner(x_corner: i32, y_corner: i32, circles: Vec<Vec<i32>>) -> bool {
let n = circles.len();
let mut vis = vec![false; n];
let in_circle = |x: i64, y: i64, cx: i64, cy: i64, r: i64| -> bool {
(x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r
};
let cross_left_top = |cx: i64, cy: i64, r: i64| -> bool {
let a = cx.abs() <= r && (cy >= 0 && cy <= y_corner as i64);
let b = (cy - y_corner as i64).abs() <= r && (cx >= 0 && cx <= x_corner as i64);
a || b
};
let cross_right_bottom = |cx: i64, cy: i64, r: i64| -> bool {
let a = (cx - x_corner as i64).abs() <= r && (cy >= 0 && cy <= y_corner as i64);
let b = cy.abs() <= r && (cx >= 0 && cx <= x_corner as i64);
a || b
};
fn dfs(
circles: &Vec<Vec<i32>>,
vis: &mut Vec<bool>,
i: usize,
x_corner: i32,
y_corner: i32,
cross_right_bottom: &dyn Fn(i64, i64, i64) -> bool,
) -> bool {
let c = &circles[i];
let (x1, y1, r1) = (c[0] as i64, c[1] as i64, c[2] as i64);
if cross_right_bottom(x1, y1, r1) {
return true;
}
vis[i] = true;
for j in 0..circles.len() {
if vis[j] {
continue;
}
let c2 = &circles[j];
let (x2, y2, r2) = (c2[0] as i64, c2[1] as i64, c2[2] as i64);
if (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2) {
continue;
}
if x1 * r2 + x2 * r1 < (r1 + r2) * x_corner as i64
&& y1 * r2 + y2 * r1 < (r1 + r2) * y_corner as i64
&& dfs(circles, vis, j, x_corner, y_corner, cross_right_bottom)
{
return true;
}
}
false
}
for i in 0..n {
let c = &circles[i];
let (x, y, r) = (c[0] as i64, c[1] as i64, c[2] as i64);
if in_circle(0, 0, x, y, r) || in_circle(x_corner as i64, y_corner as i64, x, y, r) {
return false;
}
if !vis[i]
&& cross_left_top(x, y, r)
&& dfs(
&circles,
&mut vis,
i,
x_corner,
y_corner,
&cross_right_bottom,
)
{
return false;
}
}
true
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Check if the Rectangle Corner Is Reachable easy or hard?
Check if the Rectangle Corner Is Reachable is classified as a Hard problem. It combines geometry, graph traversal, and connectivity reasoning, making it challenging without recognizing the union-find barrier concept.
Check if the Rectangle Corner Is Reachable Python/Java solution
The solution can be implemented in Python, Java, C++, C#, or JavaScript. The BFS method uses a queue to explore reachable grid cells, while the optimized solution uses arrays for Union-Find and distance formulas to detect circle overlaps.
How to solve Check if the Rectangle Corner Is Reachable in O(n^2)?
Use a mathematical approach that checks pairwise circle overlap. If the distance between two circle centers is less than or equal to the sum of their radii, union them in a Disjoint Set. Then verify whether any connected component touches rectangle boundaries in a way that blocks the path from start to destination.
What is the best approach for Check if the Rectangle Corner Is Reachable?
The most efficient solution uses geometric distance checks combined with Union-Find. Circles are treated as nodes, and overlapping circles are grouped into connected components. If a component forms a barrier touching critical rectangle boundaries, it blocks the path. This approach runs in O(n^2) time and O(n) space.
Is Check if the Rectangle Corner Is Reachable asked at Google/Amazon/Meta?
Geometry and graph connectivity problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants that combine BFS, Union-Find, and geometric constraints are especially common in system-level algorithm interviews.
What data structure is used in Check if the Rectangle Corner Is Reachable?
Common data structures include queues for BFS traversal and Disjoint Set Union (Union-Find) for grouping overlapping circles. The optimized approach mainly relies on Union-Find along with mathematical distance calculations.
What is the time complexity of Check if the Rectangle Corner Is Reachable?
The grid BFS approach takes O(W × H) time and space because every grid cell may be visited. The optimized geometric solution compares circle pairs and runs in O(n^2) time with O(n) space using Union-Find.