3235. Check if the Rectangle Corner Is Reachable

HardDepth-First SearchBreadth-First SearchUnion FindGeometryArrayMath

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The problem involves checking whether there is a valid path from the bottom-left to the top-right of a rectangle that avoids all given circles. The key considerations are:

Single Circle Blocking: If a circle contains either the start or end of the required path (either point (0, 0) or point (xCorner, yCorner) is inside a circle), there can be no valid path. Similarly, if a circle cuts across the rectangle from the left/top to the right/bottom without any route to traverse around it, it blocks the path entirely.
Multiple Circles Intersecting: When dealing with several circles, we need to check if they overlap in such a way that they form a continuous "barrier" from one end of the rectangle to the other. If they do, the combined area they cover can also potentially block the path.
DFS for Connectivity: To efficiently determine if any such barrier exists, a depth-first search (DFS) approach is used. The DFS checks if circles are connected through intersections and if this chain of connected circles spans the rectangle in a blocking manner.

The solution checks every circle to determine if they interfere with the path from the bottom-left corner to the top-right. If any circle influences the two corners such that traversal is blocked, then no valid path exists. The check uses geometric conditions based on the radius and position of each circle relative to the rectangle's boundaries to decide if they intersect with the sides in a blocking manner.

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

Solution Approach

The solution to the problem involves using a depth-first search (DFS) approach combined with some geometric checks to determine if a valid path exists. Here's a detailed breakdown of the solution:

Basic Geometric Calculations:
- We define a helper function in_circle(x, y, cx, cy, r) to check if a given point (x, y) lies inside a circle centered at (cx, cy) with radius r.
- The function computes whether (x - cx)^2 + (y - cy)^2 <= r^2, which is the standard equation for a point being inside or on the boundary of a circle.
Circle and Rectangle Intersection:
- Two functions, cross_left_top(cx, cy, r) and cross_right_bottom(cx, cy, r), determine if a circle intersects both the left or top and the right or bottom boundaries of the rectangle.
- These functions are used to check if a circle creates an obstacle path. For example, in cross_left_top, it checks if the circle crosses above the x-axis (left) or below the y = yCorner line (top), allowing evaluation of potential blockage from these sides.
Depth-First Search (DFS) for Circle Connectivity:
- A recursive function dfs(i) is designed to explore circles starting from a given circle indexed by i.
- This function checks if the current circle intersects the right or bottom of the rectangle (signifying a potential block). If so, it returns true.
- It marks the current circle as visited and then explores all adjacent circles that haven't been visited yet.
- If a circle j intersects with circle i and an intersection point lies inside the rectangle, the search continues recursively from j.
- The geometric condition for intersection is given by (x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2.
Main Logic:
- Initially, an array vis keeps track of visited circles.
- Iterate over all circles to check basic blocking conditions: whether either rectangle corner is inside a circle or if a circle creates a left/top to right/bottom barrier using the cross_left_top and DFS starting at circles that intersect this path.
- Return false immediately if any such conditions are triggered, indicating a block.
Conclusion:
- If no path is blocked after examining all circles and potential intersections, return true, indicating a viable path from the bottom-left to the top-right.

The problem is efficiently approached using both mathematical checks for intersections and DFS to identify potential circle networks that would block the given path across the rectangle.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Consider an example where the rectangle is defined with corners at (0, 0) and (10, 10), and we have two circles: circles = [[2, 5, 3], [7, 5, 3]]. These circles are centered at (2, 5) and (7, 5) each with a radius of 3.

Let's use the solution approach to determine if there is a valid path from (0, 0) to (10, 10):

Basic Geometric Calculations:
- Define a function in_circle(x, y, cx, cy, r) to check if a point lies within a circle. For instance, the point (0, 0) is not inside the circle at (2, 5), as (0 - 2)² + (0 - 5)² = 29, which is greater than 3² = 9.
Circle and Rectangle Intersection:
- For the circle centered at (2, 5), use cross_left_top(2, 5, 3). It checks if the circle crosses both the left (x = 0) and top (y = 10) boundaries or spans beyond them. Here, the circle captures points from (2-3, 5) to (2+3, 5), but it does not block a path entirely because it doesn't reach the top or bottom edges.
- Similarly, for the circle centered at (7, 5), cross_right_bottom(7, 5, 3) checks if it crosses the right (x = 10) or bottom (y = 0). It spans horizontally from (7-3, 5) to (7+3, 5) and vertically from (7, 5-3) to (7, 5+3).
Depth-First Search (DFS) for Circle Connectivity:
- Perform dfs on each circle starting from unvisited ones. For circle (2, 5), check its intersection with circle (7, 5) based on (2-7)² + (5-5)² = 25, which is less than or equal to (3+3)² = 36. Thus, they intersect.
- Mark these circles as visited and see if the overlapping segment crosses from left/top to right/bottom in a blocking manner. Since they do span horizontally across the center, check further DFS paths.
Main Logic:
- No individual circle contains a rectangle corner; however, their collective intersection spans horizontally, splitting the middle section of the rectangle. Hence, if DFS proves connectivity through intersections, conclude existence of a blockade across the complete path.
Conclusion:
- In this case, the circles form a barrier in the central part, blocking a straight path from one corner to the other. Therefore, return false as no valid path exists that would traverse around or between the circle configurations.

This walkthrough illustrates the systematic approach of checking individual circles and their potential combined barrier effects using DFS to determine path viability through a rectangular grid.

Solution Implementation

1from typing import List
2
3class Solution:
4    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
5        # Check if a point (x, y) is inside or on the boundary of a circle centered at (cx, cy) with radius r
6        def in_circle(x: int, y: int, cx: int, cy: int, r: int) -> bool:
7            return (x - cx) ** 2 + (y - cy) ** 2 <= r ** 2
8
9        # Check if a circle intersects the left or top boundary from a point (0, 0) to (xCorner, yCorner)
10        def cross_left_top(cx: int, cy: int, r: int) -> bool:
11            within_left = abs(cx) <= r and 0 <= cy <= yCorner
12            within_top = abs(cy - yCorner) <= r and 0 <= cx <= xCorner
13            return within_left or within_top
14
15        # Check if a circle intersects the right or bottom boundary finishing at (xCorner, yCorner)
16        def cross_right_bottom(cx: int, cy: int, r: int) -> bool:
17            within_right = abs(cx - xCorner) <= r and 0 <= cy <= yCorner
18            within_bottom = abs(cy) <= r and 0 <= cx <= xCorner
19            return within_right or within_bottom
20
21        # Depth-first search to check if a path exists from the top-left to the bottom-right via overlapping circles
22        def dfs(i: int) -> bool:
23            x1, y1, r1 = circles[i]
24            # If the current circle directly touches the right or bottom edge, return True
25            if cross_right_bottom(x1, y1, r1):
26                return True
27            # Mark the current circle as visited
28            visited[i] = True
29            # Check for connections with other circles
30            for j, (x2, y2, r2) in enumerate(circles):
31                # Continue if already visited or not overlapping
32                if visited[j] or not ((x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r1 + r2) ** 2):
33                    continue
34                # Both points of interest are within bounds and continue DFS if true
35                if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner) and \
36                   (y1 * r2 + y2 * r1 < (r1 + r2) * yCorner) and dfs(j):
37                    return True
38            return False
39
40        visited = [False] * len(circles)
41        # Loop through each circle and check for initial conditions
42        for i, (x, y, r) in enumerate(circles):
43            # If the circle overlaps with the starting or ending corner, obstruct the path
44            if in_circle(0, 0, x, y, r) or in_circle(xCorner, yCorner, x, y, r):
45                return False
46            # Start DFS search for any unvisited circles that cross the initial boundaries
47            if not visited[i] and cross_left_top(x, y, r) and dfs(i):
48                return False
49        return True
50

1class Solution {
2    // These are instance variables to store the positions of circles
3    // and the target corner we want to reach
4    private int[][] circles;
5    private int xCorner, yCorner;
6    private boolean[] visited; // To track visited circles during DFS
7  
8    // Main function to determine if we can reach the corner
9    public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
10        int n = circles.length;
11        // Initialize the instance variables
12        this.circles = circles;
13        this.xCorner = xCorner;
14        this.yCorner = yCorner;
15        visited = new boolean[n];
16      
17        for (int i = 0; i < n; ++i) {
18            int[] circle = circles[i];
19            int centerX = circle[0], centerY = circle[1], radius = circle[2];
20          
21            // Check if start point (0, 0) or (xCorner, yCorner) is inside any circle
22            if (inCircle(0, 0, centerX, centerY, radius) || inCircle(xCorner, yCorner, centerX, centerY, radius)) {
23                return false;
24            }
25          
26            // If circle is not visited and intersects 'left top' boundary and can reach the bottom-right corner
27            if (!visited[i] && crossLeftTop(centerX, centerY, radius) && dfs(i)) {
28                return false;
29            }
30        }
31        return true;
32    }
33  
34    // Helper function to check if point (x, y) is inside the circle with center (cx, cy) and radius r
35    private boolean inCircle(long x, long y, long centerX, long centerY, long radius) {
36        return (x - centerX) * (x - centerX) + (y - centerY) * (y - centerY) <= radius * radius;
37    }
38  
39    // Check if circle intersects the left or top boundary of the area
40    private boolean crossLeftTop(long centerX, long centerY, long radius) {
41        boolean conditionA = Math.abs(centerX) <= radius && (centerY >= 0 && centerY <= yCorner);
42        boolean conditionB = Math.abs(centerY - yCorner) <= radius && (centerX >= 0 && centerX <= xCorner);
43        return conditionA || conditionB;
44    }
45  
46    // Check if circle intersects the right or bottom boundary of the area
47    private boolean crossRightBottom(long centerX, long centerY, long radius) {
48        boolean conditionA = Math.abs(centerX - xCorner) <= radius && (centerY >= 0 && centerY <= yCorner);
49        boolean conditionB = Math.abs(centerY) <= radius && (centerX >= 0 && centerX <= xCorner);
50        return conditionA || conditionB;
51    }
52  
53    // DFS method to explore all connected circles and check if they can reach the bottom-right corner
54    private boolean dfs(int i) {
55        int[] currentCircle = circles[i];
56        long x1 = currentCircle[0], y1 = currentCircle[1], r1 = currentCircle[2];
57      
58        // Check if this circle intersects the right-bottom boundary
59        if (crossRightBottom(x1, y1, r1)) {
60            return true;
61        }
62      
63        visited[i] = true;
64      
65        for (int j = 0; j < circles.length; ++j) {
66            if (visited[j]) {
67                continue;
68            }
69          
70            int[] otherCircle = circles[j];
71            long x2 = otherCircle[0], y2 = otherCircle[1], r2 = otherCircle[2];
72          
73            // Check if circles i and j are adjacent (intersecting or touching)
74            if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2)) {
75                continue;
76            }
77          
78            // Check if they potentially form a path towards (xCorner, yCorner)
79            if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner && y1 * r2 + y2 * r2 < (r1 + r2) * yCorner && dfs(j)) {
80                return true;
81            }
82        }
83      
84        return false;
85    }
86}
87

1#include <vector>
2#include <cmath>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    bool canReachCorner(int xCorner, int yCorner, vector<vector<int>>& circles) {
10        using ll = long long;
11      
12        // Check if point (x, y) is inside the circle with center (cx, cy) and radius r
13        auto inCircle = [&](ll x, ll y, ll cx, ll cy, ll r) {
14            return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
15        };
16
17        // Check if the circle crosses the left or top boundary of the grid
18        auto crossLeftTop = [&](ll cx, ll cy, ll r) {
19            bool a = abs(cx) <= r && (cy >= 0 && cy <= yCorner);
20            bool b = abs(cy - yCorner) <= r && (cx >= 0 && cx <= xCorner);
21            return a || b;
22        };
23
24        // Check if the circle crosses the right or bottom boundary of the grid
25        auto crossRightBottom = [&](ll cx, ll cy, ll r) {
26            bool a = abs(cx - xCorner) <= r && (cy >= 0 && cy <= yCorner);
27            bool b = abs(cy) <= r && (cx >= 0 && cx <= xCorner);
28            return a || b;
29        };
30
31        int n = circles.size();
32        vector<bool> visited(n); // To track visited circles
33
34        // Depth First Search function to explore connectivity of circles
35        function<bool(int)> dfs = [&](int i) -> bool {
36            auto circle = circles[i];
37            ll x1 = circle[0], y1 = circle[1], r1 = circle[2];
38          
39            // If the circle crosses the right-bottom boundary, return true
40            if (crossRightBottom(x1, y1, r1)) {
41                return true;
42            }
43
44            visited[i] = true;
45          
46            for (int j = 0; j < n; ++j) {
47                if (visited[j]) {
48                    continue;
49                }
50                auto circle2 = circles[j];
51                ll x2 = circle2[0], y2 = circle2[1], r2 = circle2[2];
52
53                // If circles are not adjacent, skip
54                if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) > (r1 + r2) * (r1 + r2)) {
55                    continue;
56                }
57
58                // Check if both circles are not reaching beyond the boundary and recurse
59                if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner && y1 * r2 + y2 * r1 < (r1 + r2) * yCorner && dfs(j)) {
60                    return true;
61                }
62            }
63            return false;
64        };
65
66        // Iterate through each circle to check reachability conditions
67        for (int i = 0; i < n; ++i) {
68            auto circle = circles[i];
69            ll x = circle[0], y = circle[1], r = circle[2];
70
71            // If start or end corner is inside any circle, return early
72            if (inCircle(0, 0, x, y, r) || inCircle(xCorner, yCorner, x, y, r)) {
73                return false;
74            }
75
76            // If the circle at this index is not visited and crosses the left-top boundary, start a DFS
77            if (!visited[i] && crossLeftTop(x, y, r) && dfs(i)) {
78                return false;
79            }
80        }
81        return true;
82    }
83};
84

1// Function to determine if we can reach the corner (xCorner, yCorner) without going inside any given circle
2function canReachCorner(xCorner: number, yCorner: number, circles: number[][]): boolean {
3
4    // Helper function to check if a point (x, y) is inside a circle with center (cx, cy) and radius r
5    const inCircle = (x: bigint, y: bigint, cx: bigint, cy: bigint, r: bigint): boolean => {
6        const dx = x - cx;
7        const dy = y - cy;
8        return dx * dx + dy * dy <= r * r;
9    };
10
11    // Check if a circle crosses the path from the left or top boundary to the top-left corner
12    const crossLeftTop = (cx: bigint, cy: bigint, r: bigint): boolean => {
13        const crossesLeft = (BigInt(Math.abs(Number(cx))) <= r) && (cy >= 0n) && (cy <= BigInt(yCorner));
14        const crossesTop = (BigInt(Math.abs(Number(cy - BigInt(yCorner)))) <= r) &&
15                           (cx >= 0n) && (cx <= BigInt(xCorner));
16        return crossesLeft || crossesTop;
17    };
18
19    // Check if a circle crosses the path from the right or bottom boundary to the bottom-right corner
20    const crossRightBottom = (cx: bigint, cy: bigint, r: bigint): boolean => {
21        const crossesRight = (BigInt(Math.abs(Number(cx - BigInt(xCorner)))) <= r) &&
22                             (cy >= 0n) && (cy <= BigInt(yCorner));
23        const crossesBottom = (BigInt(Math.abs(Number(cy))) <= r) && 
24                              (cx >= 0n) && (cx <= BigInt(xCorner));
25        return crossesRight || crossesBottom;
26    };
27
28    const n = circles.length;
29    const visited: boolean[] = new Array(n).fill(false); // Array to keep track of visited circles
30
31    // Depth-first search to explore possible paths from one circle to another
32    const dfs = (i: number): boolean => {
33        const [x1, y1, r1] = circles[i].map(BigInt);
34        if (crossRightBottom(x1, y1, r1)) {
35            return true; // Directly reaches the bottom-right corner
36        }
37        visited[i] = true;
38        for (let j = 0; j < n; j++) {
39            if (visited[j]) continue;
40            const [x2, y2, r2] = circles[j].map(BigInt);
41            const distanceSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
42            const radiusSumSquared = (r1 + r2) * (r1 + r2);
43            if (distanceSquared > radiusSumSquared) {
44                continue; // No overlap between circles
45            }
46
47            // Check potential paths between circles and if they are within bounds
48            if (x1 * r2 + x2 * r1 < (r1 + r2) * BigInt(xCorner) &&
49                y1 * r2 + y2 * r1 < (r1 + r2) * BigInt(yCorner) &&
50                dfs(j)) {
51                return true;
52            }
53        }
54        return false; // No valid path found from this circle
55    };
56
57    for (let i = 0; i < n; i++) {
58        const [x, y, r] = circles[i].map(BigInt);
59        // If the starting or ending corner is inside a circle, reaching the corner is not possible
60        if (inCircle(0n, 0n, x, y, r) || inCircle(BigInt(xCorner), BigInt(yCorner), x, y, r)) {
61            return false;
62        }
63        // Start DFS from circles that cross the path to the top-left corner
64        if (!visited[i] && crossLeftTop(x, y, r) && dfs(i)) {
65            return false;
66        }
67    }
68
69    return true; // No path crosses any circle, reaching the corner is possible
70}
71

Time and Space Complexity

The time complexity of the code is O(n^2). This complexity arises because each circle can potentially trigger a depth-first search (DFS) operation, and during each DFS operation, each circle is checked to see if it can be reached from the current circle. This results in a potential comparison of every pair of circles, leading to O(n * n) operations in the worst case.

The space complexity of the code is O(n). This complexity is due to the use of the vis list, which keeps track of whether each circle has been visited during the DFS traversal. The vis list requires space proportional to the number of circles, hence O(n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls