3235. Check if the Rectangle Corner Is Reachable

HardDepth-First SearchBreadth-First SearchUnion FindGeometryArrayMath
Leetcode Link

Problem Description

You are given a rectangle with its bottom-left corner at the origin (0, 0) and top-right corner at (xCorner, yCorner). You are also given an array of circles, where each circle is defined by circles[i] = [xi, yi, ri] representing a circle with center at (xi, yi) and radius ri.

Your task is to determine whether there exists a path from the bottom-left corner (0, 0) to the top-right corner (xCorner, yCorner) that satisfies these conditions:

  1. The entire path must lie inside the rectangle
  2. The path must not touch or pass through any circle (including the circles' boundaries)
  3. The path can only touch the rectangle at the two corner points (start and end)

Return true if such a path exists, and false otherwise.

Essentially, you need to check if the circles block all possible paths from the bottom-left to the top-right corner of the rectangle. The circles act as obstacles that cannot be touched or crossed. If the circles form a barrier that completely blocks passage from one corner to the other, or if either corner point is inside a circle, then no valid path exists.

For example:

  • If a circle contains either the starting point (0, 0) or ending point (xCorner, yCorner), no path is possible
  • If circles connect to form a barrier from the left/top edges to the right/bottom edges of the rectangle, they block all paths
  • If there's a gap between the circles and rectangle edges that allows passage, a valid path exists

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem can be modeled as a graph where circles that intersect or touch form connections. We need to determine if these connected circles create a barrier blocking the path from bottom-left to top-right corner.

Is it a tree?

  • No: The graph formed by intersecting circles is not necessarily a tree. Circles can form cycles when multiple circles intersect with each other.

Is the problem related to directed acyclic graphs?

  • No: The connections between circles are undirected (if circle A intersects circle B, then B also intersects A), and the graph may contain cycles.

Is the problem related to shortest paths?

  • No: We're not looking for the shortest path. We only need to determine if ANY valid path exists from corner to corner.

Does the problem involve connectivity?

  • Yes: The core of the problem is about connectivity - specifically, whether the circles form a connected barrier from the left/top edges to the right/bottom edges of the rectangle, which would block all paths.

Does the problem have small constraints?

  • Yes: While not explicitly stated in the problem description, the constraints are typically manageable enough to allow DFS exploration of connected circles.

DFS/backtracking?

  • Yes: DFS is perfect for exploring connected components of circles to determine if they form a blocking barrier.

Conclusion: The flowchart suggests using DFS to explore the connectivity between circles. We start DFS from circles that touch the left or top edges of the rectangle and check if we can reach circles that touch the right or bottom edges. If such a path of connected circles exists, it forms a barrier blocking all paths from the bottom-left to top-right corner.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to think about when a path is blocked rather than when it exists. Imagine the circles as obstacles in the rectangle. A path from (0, 0) to (xCorner, yCorner) is impossible if:

  1. Either corner is inside a circle - The path cannot start or end if the corners are blocked.

  2. Circles form a "wall" across the rectangle - If circles connect to create a barrier from the left/top edges to the right/bottom edges, they completely block passage.

Think of it like trying to cross a river (the rectangle) from bottom-left to top-right. If there are stepping stones (circles) that form a complete bridge from one bank (left or top edge) to the opposite bank (right or bottom edge), you cannot cross the river without touching the stones.

The clever part is recognizing that we don't need to find the actual path - we just need to check if such a blocking wall exists. This transforms the problem into a connectivity problem: Are there connected circles that span from one side to the opposite side?

We use DFS to explore these connections:

  • Start from any circle touching the left or top edges (potential wall starting points)
  • Follow connections to neighboring circles (circles that intersect)
  • If we reach a circle touching the right or bottom edges, we've found a complete wall

Two circles are connected if they intersect, which happens when the distance between their centers is at most the sum of their radii: (x1 - x2)² + (y1 - y2)² ≤ (r1 + r2)².

The mathematical trick for checking if circles truly block the path inside the rectangle involves finding an intersection point. We calculate a weighted average point based on the radii: if circles with centers (x1, y1) and (x2, y2) and radii r1 and r2 intersect, we check if the point ((x1*r2 + x2*r1)/(r1+r2), (y1*r2 + y2*r1)/(r1+r2)) lies within the rectangle. This ensures we only consider connections that actually affect paths inside the rectangle.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Math patterns.

Solution Implementation

1class Solution: 2 def canReachCorner( 3 self, xCorner: int, yCorner: int, circles: List[List[int]] 4 ) -> bool: 5 """ 6 Determines if a path exists from (0, 0) to (xCorner, yCorner) 7 avoiding all given circles. 8 9 Args: 10 xCorner: x-coordinate of the target corner 11 yCorner: y-coordinate of the target corner 12 circles: List of circles, each defined as [center_x, center_y, radius] 13 14 Returns: 15 True if a path exists, False otherwise 16 """ 17 18 def is_point_inside_circle(point_x: int, point_y: int, 19 circle_x: int, circle_y: int, radius: int) -> bool: 20 """Check if a point is inside or on the boundary of a circle.""" 21 distance_squared = (point_x - circle_x) ** 2 + (point_y - circle_y) ** 2 22 return distance_squared <= radius ** 2 23 24 def intersects_left_or_top_boundary(circle_x: int, circle_y: int, radius: int) -> bool: 25 """ 26 Check if circle intersects with left boundary (x=0) or top boundary (y=yCorner). 27 These boundaries form the starting edges of the rectangle. 28 """ 29 # Check intersection with left boundary (x=0) for y in [0, yCorner] 30 intersects_left = abs(circle_x) <= radius and 0 <= circle_y <= yCorner 31 32 # Check intersection with top boundary (y=yCorner) for x in [0, xCorner] 33 intersects_top = abs(circle_y - yCorner) <= radius and 0 <= circle_x <= xCorner 34 35 return intersects_left or intersects_top 36 37 def intersects_right_or_bottom_boundary(circle_x: int, circle_y: int, radius: int) -> bool: 38 """ 39 Check if circle intersects with right boundary (x=xCorner) or bottom boundary (y=0). 40 These boundaries form the ending edges of the rectangle. 41 """ 42 # Check intersection with right boundary (x=xCorner) for y in [0, yCorner] 43 intersects_right = abs(circle_x - xCorner) <= radius and 0 <= circle_y <= yCorner 44 45 # Check intersection with bottom boundary (y=0) for x in [0, xCorner] 46 intersects_bottom = abs(circle_y) <= radius and 0 <= circle_x <= xCorner 47 48 return intersects_right or intersects_bottom 49 50 def depth_first_search(circle_index: int) -> bool: 51 """ 52 DFS to check if there's a connected path of circles from left/top to right/bottom. 53 Such a path would block movement from (0,0) to (xCorner, yCorner). 54 55 Returns True if current circle leads to a blocking path. 56 """ 57 current_x, current_y, current_radius = circles[circle_index] 58 59 # If this circle touches right or bottom boundary, we found a blocking path 60 if intersects_right_or_bottom_boundary(current_x, current_y, current_radius): 61 return True 62 63 # Mark current circle as visited 64 visited[circle_index] = True 65 66 # Check all other circles 67 for next_index, (next_x, next_y, next_radius) in enumerate(circles): 68 # Skip if already visited 69 if visited[next_index]: 70 continue 71 72 # Check if circles are connected (touching or overlapping) 73 distance_squared = (current_x - next_x) ** 2 + (current_y - next_y) ** 2 74 sum_radii_squared = (current_radius + next_radius) ** 2 75 76 if distance_squared > sum_radii_squared: 77 continue # Circles don't touch 78 79 # Additional pruning: check if the connection might lead to target 80 # Using weighted average position to estimate if path trends toward target 81 weighted_x = current_x * next_radius + next_x * current_radius 82 weighted_y = current_y * next_radius + next_y * current_radius 83 total_radius = current_radius + next_radius 84 85 if (weighted_x < total_radius * xCorner and 86 weighted_y < total_radius * yCorner and 87 depth_first_search(next_index)): 88 return True 89 90 return False 91 92 # Initialize visited array for DFS 93 visited = [False] * len(circles) 94 95 # Check each circle 96 for index, (center_x, center_y, radius) in enumerate(circles): 97 # If start or end point is inside a circle, path is impossible 98 if (is_point_inside_circle(0, 0, center_x, center_y, radius) or 99 is_point_inside_circle(xCorner, yCorner, center_x, center_y, radius)): 100 return False 101 102 # If circle touches left/top boundary and creates a blocking path to right/bottom 103 if (not visited[index] and 104 intersects_left_or_top_boundary(center_x, center_y, radius) and 105 depth_first_search(index)): 106 return False 107 108 # No blocking path found, so we can reach the corner 109 return True 110
1class Solution { 2 private int[][] circles; 3 private int xCorner; 4 private int yCorner; 5 private boolean[] visited; 6 7 /** 8 * Determines if it's possible to reach from (0,0) to (xCorner, yCorner) without touching any circles 9 * @param xCorner x-coordinate of the target corner 10 * @param yCorner y-coordinate of the target corner 11 * @param circles array of circles, each represented as [x, y, radius] 12 * @return true if path exists, false otherwise 13 */ 14 public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) { 15 int n = circles.length; 16 this.circles = circles; 17 this.xCorner = xCorner; 18 this.yCorner = yCorner; 19 this.visited = new boolean[n]; 20 21 for (int i = 0; i < n; i++) { 22 int[] circle = circles[i]; 23 int centerX = circle[0]; 24 int centerY = circle[1]; 25 int radius = circle[2]; 26 27 // Check if start or end point is inside this circle 28 if (inCircle(0, 0, centerX, centerY, radius) || 29 inCircle(xCorner, yCorner, centerX, centerY, radius)) { 30 return false; 31 } 32 33 // Check if circle blocks path from left/top edge and can connect to right/bottom edge 34 if (!visited[i] && crossLeftTop(centerX, centerY, radius) && dfs(i)) { 35 return false; 36 } 37 } 38 return true; 39 } 40 41 /** 42 * Checks if a point (x, y) is inside or on the boundary of a circle 43 * @param x x-coordinate of the point 44 * @param y y-coordinate of the point 45 * @param centerX x-coordinate of circle center 46 * @param centerY y-coordinate of circle center 47 * @param radius radius of the circle 48 * @return true if point is inside or on the circle 49 */ 50 private boolean inCircle(long x, long y, long centerX, long centerY, long radius) { 51 long distanceSquared = (x - centerX) * (x - centerX) + (y - centerY) * (y - centerY); 52 return distanceSquared <= radius * radius; 53 } 54 55 /** 56 * Checks if circle intersects with left or top boundary of the rectangle 57 * @param centerX x-coordinate of circle center 58 * @param centerY y-coordinate of circle center 59 * @param radius radius of the circle 60 * @return true if circle crosses left or top boundary 61 */ 62 private boolean crossLeftTop(long centerX, long centerY, long radius) { 63 // Check intersection with left boundary (x = 0) 64 boolean crossesLeft = Math.abs(centerX) <= radius && 65 centerY >= 0 && centerY <= yCorner; 66 67 // Check intersection with top boundary (y = yCorner) 68 boolean crossesTop = Math.abs(centerY - yCorner) <= radius && 69 centerX >= 0 && centerX <= xCorner; 70 71 return crossesLeft || crossesTop; 72 } 73 74 /** 75 * Checks if circle intersects with right or bottom boundary of the rectangle 76 * @param centerX x-coordinate of circle center 77 * @param centerY y-coordinate of circle center 78 * @param radius radius of the circle 79 * @return true if circle crosses right or bottom boundary 80 */ 81 private boolean crossRightBottom(long centerX, long centerY, long radius) { 82 // Check intersection with right boundary (x = xCorner) 83 boolean crossesRight = Math.abs(centerX - xCorner) <= radius && 84 centerY >= 0 && centerY <= yCorner; 85 86 // Check intersection with bottom boundary (y = 0) 87 boolean crossesBottom = Math.abs(centerY) <= radius && 88 centerX >= 0 && centerX <= xCorner; 89 90 return crossesRight || crossesBottom; 91 } 92 93 /** 94 * DFS to find if there's a connected path of circles from left/top to right/bottom 95 * @param i index of current circle 96 * @return true if path exists to right/bottom boundary 97 */ 98 private boolean dfs(int i) { 99 int[] currentCircle = circles[i]; 100 long x1 = currentCircle[0]; 101 long y1 = currentCircle[1]; 102 long r1 = currentCircle[2]; 103 104 // Check if current circle reaches right or bottom boundary 105 if (crossRightBottom(x1, y1, r1)) { 106 return true; 107 } 108 109 visited[i] = true; 110 111 // Check all other circles for connections 112 for (int j = 0; j < circles.length; j++) { 113 if (visited[j]) { 114 continue; 115 } 116 117 int[] otherCircle = circles[j]; 118 long x2 = otherCircle[0]; 119 long y2 = otherCircle[1]; 120 long r2 = otherCircle[2]; 121 122 // Check if circles are too far apart to touch 123 long distanceSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); 124 long sumRadiiSquared = (r1 + r2) * (r1 + r2); 125 if (distanceSquared > sumRadiiSquared) { 126 continue; 127 } 128 129 // Additional geometric check to ensure circles block the path 130 if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner && 131 y1 * r2 + y2 * r1 < (r1 + r2) * yCorner && 132 dfs(j)) { 133 return true; 134 } 135 } 136 137 return false; 138 } 139} 140
1class Solution { 2public: 3 bool canReachCorner(int xCorner, int yCorner, vector<vector<int>>& circles) { 4 using ll = long long; 5 6 // Check if point (x, y) is inside or on the boundary of circle centered at (cx, cy) with radius r 7 auto isPointInCircle = [&](ll x, ll y, ll centerX, ll centerY, ll radius) { 8 return (x - centerX) * (x - centerX) + (y - centerY) * (y - centerY) <= radius * radius; 9 }; 10 11 // Check if circle touches or crosses the left or top boundary of the rectangle 12 auto touchesLeftOrTopBoundary = [&](ll centerX, ll centerY, ll radius) { 13 // Check if circle touches left boundary (x = 0) 14 bool touchesLeft = abs(centerX) <= radius && (centerY >= 0 && centerY <= yCorner); 15 // Check if circle touches top boundary (y = yCorner) 16 bool touchesTop = abs(centerY - yCorner) <= radius && (centerX >= 0 && centerX <= xCorner); 17 return touchesLeft || touchesTop; 18 }; 19 20 // Check if circle touches or crosses the right or bottom boundary of the rectangle 21 auto touchesRightOrBottomBoundary = [&](ll centerX, ll centerY, ll radius) { 22 // Check if circle touches right boundary (x = xCorner) 23 bool touchesRight = abs(centerX - xCorner) <= radius && (centerY >= 0 && centerY <= yCorner); 24 // Check if circle touches bottom boundary (y = 0) 25 bool touchesBottom = abs(centerY) <= radius && (centerX >= 0 && centerX <= xCorner); 26 return touchesRight || touchesBottom; 27 }; 28 29 int numCircles = circles.size(); 30 vector<bool> visited(numCircles); 31 32 // DFS to find if there's a path from circles touching left/top to circles touching right/bottom 33 auto dfs = [&](this auto&& dfs, int circleIndex) -> bool { 34 auto& currentCircle = circles[circleIndex]; 35 ll x1 = currentCircle[0], y1 = currentCircle[1], r1 = currentCircle[2]; 36 37 // If current circle touches right or bottom boundary, path is blocked 38 if (touchesRightOrBottomBoundary(x1, y1, r1)) { 39 return true; 40 } 41 42 visited[circleIndex] = true; 43 44 // Check all other circles for overlap 45 for (int j = 0; j < numCircles; ++j) { 46 if (visited[j]) { 47 continue; 48 } 49 50 auto& otherCircle = circles[j]; 51 ll x2 = otherCircle[0], y2 = otherCircle[1], r2 = otherCircle[2]; 52 53 // Check if circles don't overlap (distance between centers > sum of radii) 54 if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2)) { 55 continue; 56 } 57 58 // Additional pruning condition: check if the overlapping circles block the path 59 // This condition checks if the weighted center is within the rectangle bounds 60 if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner && 61 y1 * r2 + y2 * r1 < (r1 + r2) * yCorner && 62 dfs(j)) { 63 return true; 64 } 65 } 66 return false; 67 }; 68 69 // Main logic: check each circle 70 for (int i = 0; i < numCircles; ++i) { 71 auto& circle = circles[i]; 72 ll x = circle[0], y = circle[1], r = circle[2]; 73 74 // If start or end point is inside a circle, path is impossible 75 if (isPointInCircle(0, 0, x, y, r) || isPointInCircle(xCorner, yCorner, x, y, r)) { 76 return false; 77 } 78 79 // If circle touches left/top boundary and can connect to right/bottom, path is blocked 80 if (!visited[i] && touchesLeftOrTopBoundary(x, y, r) && dfs(i)) { 81 return false; 82 } 83 } 84 85 // No blocking path found, corner is reachable 86 return true; 87 } 88}; 89
1/** 2 * Determines if it's possible to reach from (0,0) to (xCorner, yCorner) without touching any circles 3 * @param xCorner - The x-coordinate of the target corner 4 * @param yCorner - The y-coordinate of the target corner 5 * @param circles - Array of circles, each represented as [centerX, centerY, radius] 6 * @returns true if the corner can be reached, false otherwise 7 */ 8function canReachCorner(xCorner: number, yCorner: number, circles: number[][]): boolean { 9 /** 10 * Checks if a point (x, y) is inside or on the boundary of a circle 11 * @param x - X-coordinate of the point 12 * @param y - Y-coordinate of the point 13 * @param centerX - X-coordinate of the circle center 14 * @param centerY - Y-coordinate of the circle center 15 * @param radius - Radius of the circle 16 * @returns true if the point is inside or on the circle 17 */ 18 const isPointInCircle = ( 19 x: bigint, 20 y: bigint, 21 centerX: bigint, 22 centerY: bigint, 23 radius: bigint 24 ): boolean => { 25 const deltaX = x - centerX; 26 const deltaY = y - centerY; 27 return deltaX * deltaX + deltaY * deltaY <= radius * radius; 28 }; 29 30 /** 31 * Checks if a circle intersects with the left or top boundary of the rectangle 32 * @param centerX - X-coordinate of the circle center 33 * @param centerY - Y-coordinate of the circle center 34 * @param radius - Radius of the circle 35 * @returns true if the circle crosses left or top boundary 36 */ 37 const doesCircleCrossLeftOrTop = ( 38 centerX: bigint, 39 centerY: bigint, 40 radius: bigint 41 ): boolean => { 42 // Check if circle intersects with left boundary (x = 0) 43 const crossesLeftBoundary = 44 BigInt(Math.abs(Number(centerX))) <= radius && 45 centerY >= 0n && 46 centerY <= BigInt(yCorner); 47 48 // Check if circle intersects with top boundary (y = yCorner) 49 const crossesTopBoundary = 50 BigInt(Math.abs(Number(centerY - BigInt(yCorner)))) <= radius && 51 centerX >= 0n && 52 centerX <= BigInt(xCorner); 53 54 return crossesLeftBoundary || crossesTopBoundary; 55 }; 56 57 /** 58 * Checks if a circle intersects with the right or bottom boundary of the rectangle 59 * @param centerX - X-coordinate of the circle center 60 * @param centerY - Y-coordinate of the circle center 61 * @param radius - Radius of the circle 62 * @returns true if the circle crosses right or bottom boundary 63 */ 64 const doesCircleCrossRightOrBottom = ( 65 centerX: bigint, 66 centerY: bigint, 67 radius: bigint 68 ): boolean => { 69 // Check if circle intersects with right boundary (x = xCorner) 70 const crossesRightBoundary = 71 BigInt(Math.abs(Number(centerX - BigInt(xCorner)))) <= radius && 72 centerY >= 0n && 73 centerY <= BigInt(yCorner); 74 75 // Check if circle intersects with bottom boundary (y = 0) 76 const crossesBottomBoundary = 77 BigInt(Math.abs(Number(centerY))) <= radius && 78 centerX >= 0n && 79 centerX <= BigInt(xCorner); 80 81 return crossesRightBoundary || crossesBottomBoundary; 82 }; 83 84 const circleCount = circles.length; 85 const visited: boolean[] = new Array(circleCount).fill(false); 86 87 /** 88 * Performs depth-first search to check if there's a blocking path of circles 89 * from left/top boundaries to right/bottom boundaries 90 * @param circleIndex - Index of the current circle being explored 91 * @returns true if a blocking path exists 92 */ 93 const depthFirstSearch = (circleIndex: number): boolean => { 94 const [x1, y1, r1] = circles[circleIndex].map(BigInt); 95 96 // If current circle touches right or bottom boundary, we found a blocking path 97 if (doesCircleCrossRightOrBottom(x1, y1, r1)) { 98 return true; 99 } 100 101 visited[circleIndex] = true; 102 103 // Check all other circles 104 for (let j = 0; j < circleCount; j++) { 105 if (visited[j]) continue; 106 107 const [x2, y2, r2] = circles[j].map(BigInt); 108 109 // Check if circles are too far apart to intersect 110 const distanceSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); 111 const sumOfRadiiSquared = (r1 + r2) * (r1 + r2); 112 if (distanceSquared > sumOfRadiiSquared) { 113 continue; 114 } 115 116 // Check if the intersection point is within the rectangle bounds 117 const intersectionCondition = 118 x1 * r2 + x2 * r1 < (r1 + r2) * BigInt(xCorner) && 119 y1 * r2 + y2 * r1 < (r1 + r2) * BigInt(yCorner); 120 121 if (intersectionCondition && depthFirstSearch(j)) { 122 return true; 123 } 124 } 125 126 return false; 127 }; 128 129 // Main logic: check each circle 130 for (let i = 0; i < circleCount; i++) { 131 const [x, y, r] = circles[i].map(BigInt); 132 133 // If start or end point is inside a circle, path is blocked 134 if (isPointInCircle(0n, 0n, x, y, r) || 135 isPointInCircle(BigInt(xCorner), BigInt(yCorner), x, y, r)) { 136 return false; 137 } 138 139 // If circle touches left/top boundaries and can form a blocking path to right/bottom 140 if (!visited[i] && doesCircleCrossLeftOrTop(x, y, r) && depthFirstSearch(i)) { 141 return false; 142 } 143 } 144 145 // No blocking path found, corner is reachable 146 return true; 147} 148

Solution Approach

The implementation uses DFS to detect if circles form a blocking barrier. Here's the step-by-step approach:

1. Helper Functions Setup

First, we define three helper functions:

  • in_circle(x, y, cx, cy, r): Checks if point (x, y) is inside or on the boundary of a circle with center (cx, cy) and radius r. Returns true if (x - cx)² + (y - cy)² ≤ r².

  • cross_left_top(cx, cy, r): Checks if a circle intersects with the left or top edge of the rectangle:

    • Left edge: Circle intersects if |cx| ≤ r and 0 ≤ cy ≤ yCorner
    • Top edge: Circle intersects if |cy - yCorner| ≤ r and 0 ≤ cx ≤ xCorner

  • cross_right_bottom(cx, cy, r): Checks if a circle intersects with the right or bottom edge:

    • Right edge: Circle intersects if |cx - xCorner| ≤ r and 0 ≤ cy ≤ yCorner
    • Bottom edge: Circle intersects if |cy| ≤ r and 0 ≤ cx ≤ xCorner

2. DFS Function

The dfs(i) function explores from circle i to find if it connects to circles touching the right/bottom edges:

  • If the current circle touches the right or bottom edge, return True (barrier found)
  • Mark current circle as visited
  • For each unvisited circle j:
    • Check if circles i and j intersect: (x1 - x2)² + (y1 - y2)² ≤ (r1 + r2)²
    • Check if their intersection point is inside the rectangle using the weighted average formula:
      • x1 * r2 + x2 * r1 < (r1 + r2) * xCorner (x-coordinate check)
      • y1 * r2 + y2 * r1 < (r1 + r2) * yCorner (y-coordinate check)
    • If both conditions are met, recursively call dfs(j)
    • If any recursive call returns True, propagate it up

3. Main Algorithm

Initialize a visited array vis to track explored circles. Then:

  1. Check corner containment: For each circle, verify that neither (0, 0) nor (xCorner, yCorner) is inside it. If either corner is blocked, return False.

  2. Find blocking barriers: For each unvisited circle that touches the left or top edge (potential barrier start):

    • Call dfs(i) to explore if it connects to the right or bottom edge
    • If it does, a blocking barrier exists, return False

  3. No barriers found: If no blocking barrier is detected after checking all circles, return True.

Key Data Structure:

  • Boolean array vis to track visited circles during DFS traversal, preventing infinite loops in connected components.

The algorithm's correctness relies on the observation that if circles form a continuous barrier from left/top to right/bottom edges, they must pass through the rectangle's interior, making it impossible to find a valid path from (0, 0) to (xCorner, yCorner) without touching any circle.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Setup:

  • Rectangle: bottom-left at (0, 0), top-right at (4, 3)
  • Circles: [[1, 1, 2], [3, 2, 1]]
    • Circle 1: center (1, 1), radius 2
    • Circle 2: center (3, 2), radius 1

Step 1: Check if corners are blocked

First, we check if either corner point is inside any circle:

  • For Circle 1 and point (0, 0):
    • Distance² = (0-1)² + (0-1)² = 2
    • Radius² = 4
    • Since 2 ≤ 4, point (0, 0) IS inside Circle 1!
    • Return False immediately - no path possible

Let's modify the example to make it more interesting:

  • Circles: [[2, 3, 1], [2, 0, 1]]
    • Circle 1: center (2, 3), radius 1 (touches top edge)
    • Circle 2: center (2, 0), radius 1 (touches bottom edge)

Step 1: Check corners again

  • Point (0, 0):
    • Circle 1: (0-2)² + (0-3)² = 13 > 1² ✓ Not inside
    • Circle 2: (0-2)² + (0-0)² = 4 > 1² ✓ Not inside
  • Point (4, 3):
    • Circle 1: (4-2)² + (3-3)² = 4 > 1² ✓ Not inside
    • Circle 2: (4-2)² + (3-0)² = 13 > 1² ✓ Not inside

Step 2: Check for blocking barriers

Initialize vis = [False, False]

Check Circle 1 (index 0):

  • Does it touch left or top edge?
    • Left edge: |2| = 2 > 1 and not in y-range → No
    • Top edge: |3-3| = 0 ≤ 1 and 0 ≤ 2 ≤ 4 → Yes!
  • Start DFS from Circle 1:
    • Does Circle 1 touch right or bottom edge?
      • Right edge: |2-4| = 2 > 1 → No
      • Bottom edge: |3| = 3 > 1 → No
    • Mark vis[0] = True
    • Check connection to Circle 2:
      • Distance² = (2-2)² + (3-0)² = 9
      • Sum of radii² = (1+1)² = 4
      • Since 9 > 4, circles don't intersect
    • DFS returns False

Check Circle 2 (index 1):

  • Does it touch left or top edge?
    • Left edge: |2| = 2 > 1 → No
    • Top edge: |0-3| = 3 > 1 → No
  • Skip DFS (doesn't touch left/top)

Step 3: Result No blocking barrier found → Return True

A valid path exists! One such path could curve around the circles, going from (0, 0) to the right, then up, avoiding both circles.

Alternative Example with Blocking: Let's consider circles that DO block:

  • Circles: [[1, 1.5, 1.6], [3, 1.5, 1.6]]
    • Circle 1: touches left edge, extends across
    • Circle 2: touches right edge, extends across
    • They overlap in the middle

In this case:

  1. Corners are not inside circles ✓
  2. Circle 1 touches left edge, start DFS:
    • Circle 1 connects to Circle 2 (they intersect)
    • Circle 2 touches right edge
    • DFS returns True → blocking barrier found!
  3. Return False - no valid path exists

The circles form a "wall" across the rectangle, blocking all paths from bottom-left to top-right.

Time and Space Complexity

Time Complexity: O(n²)

The algorithm iterates through all circles in the outer loop (up to n circles). For each circle that crosses the left or top boundary and hasn't been visited, it calls the dfs function. Inside dfs, for each circle i, the algorithm checks all other circles j to determine if they are connected (circles overlap or touch). This results in examining up to n circles for each DFS call.

In the worst case, all circles form a connected component starting from the left/top boundary, causing the DFS to visit all n circles. For each visited circle, we check connections with all other n circles, resulting in O(n²) operations total.

The helper functions in_circle, cross_left_top, and cross_right_bottom all run in O(1) time as they perform constant-time arithmetic operations.

Space Complexity: O(n)

The space complexity consists of:

  • The vis array of size n to track visited circles: O(n)
  • The recursive call stack for DFS, which in the worst case (when all circles form a chain) can go up to depth n: O(n)

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Circle-to-Rectangle Boundary Intersection Check

A common mistake is incorrectly checking whether a circle intersects with the rectangle's boundaries. Developers often forget to constrain the intersection check to the actual boundary segments.

Pitfall Example:

# WRONG: Only checks distance to infinite line, not the bounded segment def intersects_left_boundary(cx, cy, r):  return abs(cx) <= r # Missing y-coordinate constraint!

Solution:

# CORRECT: Checks both distance AND position along the boundary def intersects_left_boundary(cx, cy, r):  return abs(cx) <= r and 0 <= cy <= yCorner

2. Floating Point Precision Issues

When checking if two circles intersect or if a point is inside a circle, using floating-point arithmetic can lead to precision errors, especially with large coordinates.

Pitfall Example:

# WRONG: Using sqrt can introduce floating point errors import math distance = math.sqrt((x1 - x2)**2 + (y1 - y2)**2) if distance <= r1 + r2: # Precision issues!  # circles intersect

Solution:

# CORRECT: Compare squared distances to avoid sqrt distance_squared = (x1 - x2)**2 + (y1 - y2)**2 sum_radii_squared = (r1 + r2)**2 if distance_squared <= sum_radii_squared:  # circles intersect

3. Missing Edge Cases for Corner Points

Forgetting to check if the start point (0,0) or end point (xCorner, yCorner) lies inside any circle will lead to incorrect results.

Pitfall Example:

# WRONG: Only checking for blocking paths, not corner containment def canReachCorner(xCorner, yCorner, circles):  # Directly starts DFS without checking corners  for i, circle in enumerate(circles):  if intersects_left_or_top(circle) and dfs(i):  return False  return True

Solution:

# CORRECT: First check if corners are blocked def canReachCorner(xCorner, yCorner, circles):  # Check corners first  for cx, cy, r in circles:  if is_inside_circle(0, 0, cx, cy, r):  return False  if is_inside_circle(xCorner, yCorner, cx, cy, r):  return False   # Then check for blocking paths  # ... rest of the logic

4. Incorrect Boundary Pairing in DFS

A subtle mistake is checking for the wrong combination of boundaries. The blocking path must connect opposite boundary pairs to actually block movement.

Pitfall Example:

# WRONG: Checking if path connects any two boundaries def dfs(i):  if touches_any_boundary(circles[i]): # Wrong logic!  return True

Solution:

# CORRECT: Must connect (left OR top) to (right OR bottom) def dfs(i):  # Start from left/top boundaries  if intersects_right_or_bottom_boundary(circles[i]):  return True # Found blocking path

5. Inefficient Circle Intersection Within Rectangle Check

The weighted average optimization in the DFS can be confusing and lead to incorrect pruning if misunderstood.

Pitfall Example:

# WRONG: Not checking if intersection is within rectangle bounds def dfs(i):  for j in range(len(circles)):  if not visited[j] and circles_intersect(i, j):  # Missing check if intersection is inside rectangle!  if dfs(j):  return True

Solution:

# CORRECT: Verify intersection point is within rectangle def dfs(i):  for j in range(len(circles)):  if not visited[j] and circles_intersect(i, j):  # Check if intersection could be inside rectangle  weighted_x = x1 * r2 + x2 * r1  weighted_y = y1 * r2 + y2 * r1  total_r = r1 + r2   if (weighted_x < total_r * xCorner and  weighted_y < total_r * yCorner):  if dfs(j):  return True
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

DFS Fundamentals

https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More