Facebook Pixel

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

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

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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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