# Check if the Rectangle Corner Is Reachable
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-the-rectangle-corner-is-reachable)
Canonical: https://scaleengineer.com/dsa/problems/check-if-the-rectangle-corner-is-reachable
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
---
## Problem
You are given two positive integers `xCorner` and `yCorner`, and a 2D array `circles`, where `circles[i] = [xi, yi, ri]` denotes a circle with center at `(xi, yi)` and radius `ri`.

There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate `(xCorner, yCorner)`. You need to check whether there is a path from the bottom left corner to the top right corner such that the **entire path** lies inside the rectangle, **does not** touch or lie inside **any** circle, and touches the rectangle **only** at the two corners.

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

**Example 1:**

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

**Output:** true

**Explanation:**

![](https://assets.glich.co/dsa/check-if-the-rectangle-corner-is-reachable/image0.png)

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

**Example 2:**

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

**Output:** false

**Explanation:**

![](https://assets.glich.co/dsa/check-if-the-rectangle-corner-is-reachable/image1.png)

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

**Example 3:**

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

**Output:** false

**Explanation:**

![](https://assets.glich.co/dsa/check-if-the-rectangle-corner-is-reachable/image2.png)

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

**Example 4:**

**Input:** xCorner = 4, yCorner = 4, circles = \[\[5,5,1\]\]

**Output:** true

**Explanation:**

![](https://assets.glich.co/dsa/check-if-the-rectangle-corner-is-reachable/image3.png)

**Constraints:**

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

# Approaches
## Graph Traversal on Circles (BFS/DFS)
The problem can be modeled as finding a path in a graph. The nodes of the graph are the circles, and an edge exists between two circles if they overlap or touch. A path from the bottom-left to the top-right corner is blocked if there is a continuous chain of circles that separates these two corners. This occurs if a single connected component of circles touches both a "start" boundary (the left or bottom edge of the rectangle) and an "end" boundary (the top or right edge).

We can build this graph explicitly using an adjacency list and then use a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to find the connected components. For each component, we check which boundaries it touches to determine if it forms a blocking wall.
**Time:** O(N^2), where N is the number of circles. Building the adjacency list by checking all pairs of circles takes O(N^2) time. The subsequent graph traversal visits each node and edge at most once, which is O(N + E), where E is the number of edges. In the worst case, E can be O(N^2), so the total time complexity is dominated by O(N^2). · **Space:** O(N^2), where N is the number of circles. The adjacency list can store up to O(N^2) edges in a dense graph. The `visited` array and the traversal queue require O(N) space.
**Pros:** Conceptually straightforward, as it directly translates the problem into a standard graph traversal task.; Correctly identifies all blocking scenarios.
**Cons:** The space complexity is `O(N^2)` in the worst case, which can be memory-intensive for a large number of circles if the graph is dense.; Requires building and storing an explicit graph structure.
### Explanation
The algorithm proceeds as follows:

1.  **Build the Graph:** Construct an adjacency list representation of the graph. The graph has `N` nodes, where `N` is the number of circles.
    -   Iterate through every pair of circles `(i, j)`.
    -   Calculate the squared distance between their centers: `d^2 = (x_i - x_j)^2 + (y_i - y_j)^2`.
    -   Calculate the squared sum of their radii: `r_sum^2 = (r_i + r_j)^2`.
    -   If `d^2 <= r_sum^2`, the circles overlap or touch. Add an edge between node `i` and node `j` in the adjacency list. Using `long` for these calculations is crucial to avoid overflow given the constraints.

2.  **Find Connected Components and Check Boundaries:**
    -   Create a `visited` array of size `N` to keep track of visited circles.
    -   Iterate from `i = 0` to `N-1`. If circle `i` has not been visited:
        -   This marks the start of a new connected component.
        -   Initialize boolean flags: `touchesLeft`, `touchesBottom`, `touchesTop`, `touchesRight` to `false`.
        -   Start a traversal (e.g., BFS) from circle `i`. Use a queue, add `i` to it, and mark `i` as visited.
        -   While the queue is not empty, dequeue a circle `c` and check if it touches any of the four boundaries, updating the boolean flags accordingly.
        -   Add all unvisited neighbors of `c` to the queue.
        -   After the traversal for the component is complete, check if it forms a blocking wall: `if ((touchesLeft || touchesBottom) && (touchesTop || touchesRight))`, return `false`.

3.  **Return Result:** If the loop completes without finding any blocking component, it means a path exists. Return `true`.

```java
import java.util.*;

class Solution {
    public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
        int n = circles.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];
                long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
                long distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                long radiusSumSq = (r1 + r2) * (r1 + r2);
                if (distSq <= radiusSumSq) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                boolean touchesLeft = false;
                boolean touchesBottom = false;
                boolean touchesRight = false;
                boolean touchesTop = false;
                
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                visited[i] = true;
                
                while (!q.isEmpty()) {
                    int u = q.poll();
                    long x = circles[u][0], y = circles[u][1], r = circles[u][2];
                    
                    if (x <= r) touchesLeft = true;
                    if (y <= r) touchesBottom = true;
                    if (xCorner - x <= r) touchesRight = true;
                    if (yCorner - y <= r) touchesTop = true;
                    
                    for (int v : adj.get(u)) {
                        if (!visited[v]) {
                            visited[v] = true;
                            q.offer(v);
                        }
                    }
                }
                
                if ((touchesLeft || touchesBottom) && (touchesTop || touchesRight)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}
```
### Algorithm
- Create an adjacency list to represent the graph where nodes are circles.
- Iterate through all pairs of circles. If two circles overlap or touch, add an edge between them in the adjacency list.
- Use a `visited` array to track processed circles.
- Iterate through each circle. If a circle hasn't been visited, start a graph traversal (like BFS or DFS) to find its connected component.
- During the traversal for a component, maintain four boolean flags: `touchesLeft`, `touchesBottom`, `touchesTop`, `touchesRight`.
- For each circle in the component, update these flags if it touches the corresponding boundary of the rectangle.
- After a component is fully traversed, check if it forms a blocking wall. A wall exists if the component touches a "start" boundary (left or bottom) AND an "end" boundary (top or right).
- If a blocking component is found, return `false` immediately.
- If all components are checked and none are blocking, return `true`.

## Optimized Connectivity Check with Union-Find
This approach improves upon the graph traversal method by using a more space-efficient data structure for handling connectivity: the Union-Find or Disjoint Set Union (DSU). Instead of building an explicit graph, we can determine the connected components of circles on the fly.

We model the problem by considering the circles and the four boundaries of the rectangle as elements in a set. We then unite elements that are connected (i.e., overlapping circles, or circles touching a boundary). A path from `(0,0)` to `(xCorner, yCorner)` is blocked if a "start" boundary (left or bottom) becomes connected to an "end" boundary (top or right) through a chain of circles.
**Time:** O(N^2 * α(N)), where N is the number of circles and α is the inverse Ackermann function. The dominant part is iterating through O(N^2) pairs of circles. For each pair, we perform a distance calculation and potentially a DSU `union` operation, which takes O(α(N)) time on average. Since α(N) is a very slowly growing function, the complexity is effectively O(N^2). · **Space:** O(N), where N is the number of circles. The DSU data structure requires an array of size N+4 to store the parent pointers.
**Pros:** Highly space-efficient, requiring only `O(N)` space for the DSU data structure.; The logic is concise and elegant once the DSU concept is applied to the problem.; Very fast `find` and `union` operations (amortized nearly constant time).
**Cons:** The time complexity is still bottlenecked by the `O(N^2)` loop required to check for overlaps between all pairs of circles.
### Explanation
The algorithm uses a DSU data structure with `N+4` elements, where `N` is the number of circles. The first `N` elements represent the circles, and the last four represent the four boundaries of the rectangle. We can assign indices as follows:
- `0` to `N-1`: for the circles.
- `N`: Left boundary.
- `N+1`: Top boundary.
- `N+2`: Right boundary.
- `N+3`: Bottom boundary.

The algorithm proceeds as follows:
1.  **Initialize DSU:** Create a DSU data structure for `N+4` elements, where each element is initially in its own set.
2.  **Union Circles and Boundaries:** Iterate through each circle `i` from `0` to `N-1`.
    -   Check if circle `i` touches any boundaries and perform unions: `union(i, boundary_index)`.
    -   Iterate through subsequent circles `j` from `i+1` to `N-1`. If circle `i` and `j` overlap, unite their sets: `union(i, j)`.
3.  **Check for Blocking Connections:** After all unions are performed, check if any of the blocking conditions are met. The start corner `(0,0)` is associated with the left and bottom boundaries, while the end corner `(xCorner, yCorner)` is associated with the top and right boundaries. A path is blocked if a start boundary is connected to an end boundary. The specific connections to check are:
    -   Left connected to Right
    -   Left connected to Top
    -   Bottom connected to Right
    -   Bottom connected to Top
    If any of these connections exist in the DSU (i.e., their representative elements are the same), return `false`.
4.  **Return Result:** If none of the blocking conditions are met, a path exists. Return `true`.

```java
class DSU {
    private int[] parent;
    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }
}

class Solution {
    public boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
        int n = circles.length;
        // N: left, N+1: top, N+2: right, N+3: bottom
        DSU dsu = new DSU(n + 4);
        int left = n, top = n + 1, right = n + 2, bottom = n + 3;

        for (int i = 0; i < n; i++) {
            long x = circles[i][0], y = circles[i][1], r = circles[i][2];
            
            if (x <= r) dsu.union(i, left);
            if (yCorner - y <= r) dsu.union(i, top);
            if (xCorner - x <= r) dsu.union(i, right);
            if (y <= r) dsu.union(i, bottom);

            for (int j = i + 1; j < n; j++) {
                long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
                long distSq = (x - x2) * (x - x2) + (y - y2) * (y - y2);
                long radiusSumSq = (r + r2) * (r + r2);
                if (distSq <= radiusSumSq) {
                    dsu.union(i, j);
                }
            }
        }

        if (dsu.find(left) == dsu.find(right)) return false;
        if (dsu.find(left) == dsu.find(top)) return false;
        if (dsu.find(bottom) == dsu.find(right)) return false;
        if (dsu.find(bottom) == dsu.find(top)) return false;

        return true;
    }
}
```
### Algorithm
- Initialize a Disjoint Set Union (DSU) data structure for `N+4` elements. `N` elements for the circles and 4 for the boundaries (left, top, right, bottom).
- Assign unique indices to the four boundaries, for example, `N` for left, `N+1` for top, `N+2` for right, and `N+3` for bottom.
- Iterate through all pairs of circles `(i, j)`. If they overlap or touch, unite their sets using `dsu.union(i, j)`.
- Iterate through each circle `i`. Check if it touches any of the four boundaries. If it touches a boundary, unite the circle's set with the corresponding boundary's set, e.g., `dsu.union(i, N)` if it touches the left boundary.
- After all unions are performed, check for the blocking conditions by checking if any "start" boundary is in the same set as any "end" boundary.
- The blocking conditions are: `find(left) == find(right)`, `find(left) == find(top)`, `find(bottom) == find(right)`, or `find(bottom) == find(top)`.
- If any of these conditions are true, a blocking path exists, so return `false`.
- If none of the conditions are met after checking all possibilities, return `true`.

# Solutions
### Java

```java
class Solution {
private
  int[][] circles;
private
  int xCorner, yCorner;
private
  boolean[] vis;
public
  boolean canReachCorner(int xCorner, int yCorner, int[][] circles) {
    int n = circles.length;
    this.circles = circles;
    this.xCorner = xCorner;
    this.yCorner = yCorner;
    vis = new boolean[n];
    for (int i = 0; i < n; ++i) {
      var c = circles[i];
      int x = c[0], y = c[1], r = c[2];
      if (inCircle(0, 0, x, y, r) || inCircle(xCorner, yCorner, x, y, r)) {
        return false;
      }
      if (!vis[i] && crossLeftTop(x, y, r) && dfs(i)) {
        return false;
      }
    }
    return true;
  }
private
  boolean inCircle(long x, long y, long cx, long cy, long r) {
    return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
  }
private
  boolean crossLeftTop(long cx, long cy, long r) {
    boolean a = Math.abs(cx) <= r && (cy >= 0 && cy <= yCorner);
    boolean b = Math.abs(cy - yCorner) <= r && (cx >= 0 && cx <= xCorner);
    return a || b;
  }
private
  boolean crossRightBottom(long cx, long cy, long r) {
    boolean a = Math.abs(cx - xCorner) <= r && (cy >= 0 && cy <= yCorner);
    boolean b = Math.abs(cy) <= r && (cx >= 0 && cx <= xCorner);
    return a || b;
  }
private
  boolean dfs(int i) {
    var c = circles[i];
    long x1 = c[0], y1 = c[1], r1 = c[2];
    if (crossRightBottom(x1, y1, r1)) {
      return true;
    }
    vis[i] = true;
    for (int j = 0; j < circles.length; ++j) {
      var c2 = circles[j];
      long x2 = c2[0], y2 = c2[1], r2 = c2[2];
      if (vis[j]) {
        continue;
      }
      if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) >
          (r1 + r2) * (r1 + r2)) {
        continue;
      }
      if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner &&
          y1 * r2 + y2 * r1 < (r1 + r2) * yCorner && dfs(j)) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canReachCorner(int xCorner, int yCorner, vector<vector<int>> &circles) {
    using ll = long long;
    auto inCircle = [&](ll x, ll y, ll cx, ll cy, ll r) {
      return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= r * r;
    };
    auto crossLeftTop = [&](ll cx, ll cy, ll r) {
      bool a = abs(cx) <= r && (cy >= 0 && cy <= yCorner);
      bool b = abs(cy - yCorner) <= r && (cx >= 0 && cx <= xCorner);
      return a || b;
    };
    auto crossRightBottom = [&](ll cx, ll cy, ll r) {
      bool a = abs(cx - xCorner) <= r && (cy >= 0 && cy <= yCorner);
      bool b = abs(cy) <= r && (cx >= 0 && cx <= xCorner);
      return a || b;
    };
    int n = circles.size();
    vector<bool> vis(n);
    auto dfs = [&](auto &&dfs, int i) -> bool {
      auto c = circles[i];
      ll x1 = c[0], y1 = c[1], r1 = c[2];
      if (crossRightBottom(x1, y1, r1)) {
        return true;
      }
      vis[i] = true;
      for (int j = 0; j < n; ++j) {
        if (vis[j]) {
          continue;
        }
        auto c2 = circles[j];
        ll x2 = c2[0], y2 = c2[1], r2 = c2[2];
        if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) >
            (r1 + r2) * (r1 + r2)) {
          continue;
        }
        if (x1 * r2 + x2 * r1 < (r1 + r2) * xCorner &&
            y1 * r2 + y2 * r1 < (r1 + r2) * yCorner && dfs(dfs, j)) {
          return true;
        }
      }
      return false;
    };
    for (int i = 0; i < n; ++i) {
      auto c = circles[i];
      ll x = c[0], y = c[1], r = c[2];
      if (inCircle(0, 0, x, y, r) || inCircle(xCorner, yCorner, x, y, r)) {
        return false;
      }
      if (!vis[i] && crossLeftTop(x, y, r) && dfs(dfs, i)) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
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

```