#3235

Hard

LeetCode Problem Workspace

Check if the Rectangle Corner Is Reachable

Determine if there is a valid path from the bottom-left to top-right of a rectangle while avoiding circles.

array math depth first search breadth first search union find

Problem Statement

You are given a rectangle in the coordinate plane with its bottom-left corner at (0, 0) and top-right corner at (xCorner, yCorner). Additionally, you are given a list of circles where each circle is defined by its center at (xi, yi) and radius ri. The task is to check if there exists a path from the bottom-left corner to the top-right corner of the rectangle, which avoids all the circles and only touches the rectangle at the two corners.

To solve this, we need to ensure that the path remains inside the rectangle without touching or intersecting any of the circles, and that the path is valid between the two corners. Return true if such a path exists, otherwise return false.

Examples

Example 1

Input: xCorner = 3, yCorner = 4, circles = [[2,1,1]]

Output: true

The black curve shows a possible path between (0, 0) and (3, 4) .

Example 2

Input: xCorner = 3, yCorner = 3, circles = [[1,1,2]]

Output: false

No path exists from (0, 0) to (3, 3) .

Example 3

Input: xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]

Output: false

No path exists from (0, 0) to (3, 3) .

Constraints

3 <= xCorner, yCorner <= 109
1 <= circles.length <= 1000
circles[i].length == 3
1 <= xi, yi, ri <= 109

Solution Approach

Graph Representation

Model this problem using a graph where the two corners of the rectangle are treated as special vertices. Circles are also treated as obstacles that block paths. Use an algorithm like DFS or BFS to explore possible paths between the corners, while ensuring circles are avoided.

Geometry Considerations

To ensure a path avoids circles, compute whether a path would intersect any circle using geometry, such as checking if the Euclidean distance between points and circle centers is less than the radius. This check is crucial to avoid overlap.

Union-Find or BFS

Apply either BFS or a Union-Find algorithm to efficiently determine connectivity between the two corners while avoiding circles. Each connected component can represent a section of the rectangle free from obstruction, and the algorithm ensures we only consider valid paths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the method used. A BFS or DFS approach has a time complexity of O(V + E), where V is the number of vertices (including the rectangle corners and circle boundary checks), and E is the number of edges between vertices. Space complexity will similarly depend on the graph representation and the algorithm used for traversal.

What Interviewers Usually Probe

Look for an understanding of graph theory applied to geometry.
Assess the candidate's ability to efficiently handle obstacles (circles) in pathfinding.
Evaluate how well the candidate combines algorithmic approaches like DFS/BFS with mathematical geometry.

Common Pitfalls or Variants

Common pitfalls

Ignoring edge cases like when the two corners are inside a circle or when circles touch the rectangle boundaries.
Not properly handling circle intersection checks and assuming direct paths without verifying geometry.
Overcomplicating the problem with unnecessary computations instead of leveraging efficient graph traversal algorithms.

Follow-up variants

What if the rectangle's top-right corner changes dynamically during the pathfinding process?
How does the solution change when the number of circles is significantly larger (e.g., 1000+)?
How would the approach change if there were multiple rectangles or obstacles to consider simultaneously?

FAQ

How can I check if a path exists between the bottom-left and top-right corners?

You can model the problem as a graph and use algorithms like BFS or DFS to explore if there's a valid path that avoids all circles.

What geometric calculations are required to avoid circles in the path?

You need to calculate the Euclidean distance between points on the path and circle centers to ensure no intersection occurs.

What is the time complexity of the solution?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph representation.

Can this problem be solved using the Union-Find algorithm?

Yes, Union-Find can be used to efficiently determine whether the two corners are connected by a valid path avoiding obstacles.

How do I handle edge cases with circle intersections?

Ensure that before exploring a potential path, you check if it intersects any circle by comparing distances to circle centers.

terminal

Solution

Solution 1: DFS + Mathematics

According to the problem description, we discuss the following cases:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

class Solution:
    def canReachCorner(
        self, xCorner: int, yCorner: int, circles: List[List[int]]
    ) -> bool:
        def in_circle(x: int, y: int, cx: int, cy: int, r: int) -> int:
            return (x - cx) ** 2 + (y - cy) ** 2 <= r**2

        def cross_left_top(cx: int, cy: int, r: int) -> bool:
            a = abs(cx) <= r and 0 <= cy <= yCorner
            b = abs(cy - yCorner) <= r and 0 <= cx <= xCorner
            return a or b

        def cross_right_bottom(cx: int, cy: int, r: int) -> bool:
            a = abs(cx - xCorner) <= r and 0 <= cy <= yCorner
            b = abs(cy) <= r and 0 <= cx <= xCorner
            return a or b

        def dfs(i: int) -> bool:
            x1, y1, r1 = circles[i]
            if cross_right_bottom(x1, y1, r1):
                return True
            vis[i] = True
            for j, (x2, y2, r2) in enumerate(circles):
                if vis[j] or not ((x1 - x2) ** 2 + (y1 - y2) ** 2 <= (r1 + r2) ** 2):
                    continue
                if (
                    (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner)
                    and (y1 * r2 + y2 * r1 < (r1 + r2) * yCorner)
                    and dfs(j)
                ):
                    return True
            return False

        vis = [False] * len(circles)
        for i, (x, y, r) in enumerate(circles):
            if in_circle(0, 0, x, y, r) or in_circle(xCorner, yCorner, x, y, r):
                return False
            if (not vis[i]) and cross_left_top(x, y, r) and dfs(i):
                return False
        return True

Continue Practicing

#2101 detonate the maximum bombs #3493 properties graph #3607 power grid maintenance