LeetCode 3235 - Check if the Rectangle Corner Is Reachable

LeetCode Problem 3235

Difficulty: 🔴 Hard
Topics: Array, Math, Depth-First Search, Breadth-First Search, Union-Find, Geometry

Solution

Problem Understanding

The problem asks whether there is a clear, unobstructed path from the bottom-left corner (0, 0) to the top-right corner (xCorner, yCorner) of a rectangle, such that the path does not touch or go inside any given circles. Each circle is represented by its center (xi, yi) and radius ri. The path can only touch the rectangle at its corners and must remain entirely inside the rectangle boundaries. The function should return true if such a path exists and false otherwise.

The input consists of two integers representing the rectangle's top-right corner coordinates and a list of circles. The rectangle dimensions can be very large, up to 10^9, while the number of circles is modest (up to 1000). This tells us that brute-force approaches iterating over every coordinate point in the rectangle are infeasible due to the large scale. Instead, the solution must reason about geometric constraints and circle overlaps without discretizing the entire plane.

Key edge cases include: the start or end point being inside a circle, circles that touch rectangle boundaries, overlapping circles that block all potential paths, and circles that are entirely outside the rectangle (irrelevant to the path).

Approaches

A brute-force approach would discretize the rectangle into a grid of points and perform a BFS or DFS from (0, 0), marking points blocked by circles. While correct in principle, this approach is computationally impossible for large rectangles due to the 10^9 x 10^9 scale. Even sparse grids would require careful scaling, but it becomes impractical given the high coordinate ranges.

The key insight for an optimal solution is that the only points that matter for path blockage are those that intersect the rectangle's edges or corners, or those that form connected regions of circles that could potentially block the path entirely. We can model the problem as checking whether (0, 0) and (xCorner, yCorner) lie in separate connected regions blocked by circles. Using Union-Find or flood fill on a graph of circles that intersect each other and the rectangle borders allows us to determine if a path is impossible.

The main idea is: if any circle or group of connected circles fully blocks access from the start to the end by touching or overlapping the rectangle edges, the path is impossible. Otherwise, a path exists.

Algorithm Walkthrough

1. Initialize two boolean flags, blockedStart and blockedEnd, to track whether the start (0, 0) or end (xCorner, yCorner) points are inside any circle. If either is inside a circle, return false immediately.
2. Create a graph where each circle is a node. Draw an edge between two circles if their areas overlap, i.e., the distance between centers ≤ sum of radii.
3. Identify circles that touch the rectangle's bottom or left edges and top or right edges. These are "blocking" circles.
4. Perform a DFS or BFS to check whether there exists a connected group of circles that touches both start-side edges and end-side edges. If such a connected group exists, it blocks all paths, and return false.
5. If no such blocking group exists, return true.

Why it works: By reducing the problem to checking connected components of circles and their interaction with rectangle edges, we avoid simulating the entire rectangle. The invariant is that any group of circles that connects start and end edges fully blocks a path, while if no group does, at least one path exists.

Python Solution

from typing import List
from math import sqrt

class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        n = len(circles)
        
        def dist2(c1, c2):
            return (c1[0]-c2[0])**2 + (c1[1]-c2[1])**2
        
        # Check if start or end is inside any circle
        for x, y, r in circles:
            if (0-x)**2 + (0-y)**2 <= r**2 or (xCorner-x)**2 + (yCorner-y)**2 <= r**2:
                return False
        
        # Build graph of overlapping circles
        graph = [[] for _ in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if dist2(circles[i], circles[j]) <= (circles[i][2] + circles[j][2])**2:
                    graph[i].append(j)
                    graph[j].append(i)
        
        visited = [False] * n
        
        def touches_edges(circle):
            x, y, r = circle
            touchesStartEdge = x - r <= 0 or y - r <= 0
            touchesEndEdge = x + r >= xCorner or y + r >= yCorner
            return touchesStartEdge, touchesEndEdge
        
        for i in range(n):
            if not visited[i]:
                stack = [i]
                visited[i] = True
                touchesStart, touchesEnd = touches_edges(circles[i])
                while stack:
                    node = stack.pop()
                    ts, te = touches_edges(circles[node])
                    touchesStart |= ts
                    touchesEnd |= te
                    for nei in graph[node]:
                        if not visited[nei]:
                            visited[nei] = True
                            stack.append(nei)
                if touchesStart and touchesEnd:
                    return False
        return True

Implementation walkthrough: We first rule out trivial cases where the start or end is inside a circle. Then we construct a graph where edges represent overlapping circles. Using DFS, we explore each connected component, tracking whether it touches both start-side and end-side rectangle edges. If such a component exists, it blocks all paths. Otherwise, a path exists.

Go Solution

import "math"

func canReachCorner(xCorner int, yCorner int, circles [][]int) bool {
    n := len(circles)
    
    dist2 := func(c1, c2 []int) int {
        dx := c1[0] - c2[0]
        dy := c1[1] - c2[1]
        return dx*dx + dy*dy
    }
    
    // Check start/end inside circle
    for _, c := range circles {
        if (c[0]*c[0]+c[1]*c[1] <= c[2]*c[2]) || 
           ((c[0]-xCorner)*(c[0]-xCorner)+(c[1]-yCorner)*(c[1]-yCorner) <= c[2]*c[2]) {
            return false
        }
    }
    
    graph := make([][]int, n)
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            rsum := c[2] + circles[j][2]
            if dist2(circles[i], circles[j]) <= rsum*rsum {
                graph[i] = append(graph[i], j)
                graph[j] = append(graph[j], i)
            }
        }
    }
    
    visited := make([]bool, n)
    
    touchesEdges := func(c []int) (bool, bool) {
        touchesStart := c[0]-c[2] <= 0 || c[1]-c[2] <= 0
        touchesEnd := c[0]+c[2] >= xCorner || c[1]+c[2] >= yCorner
        return touchesStart, touchesEnd
    }
    
    var dfs func(int) (bool, bool)
    dfs = func(u int) (bool, bool) {
        visited[u] = true
        ts, te := touchesEdges(circles[u])
        for _, v := range graph[u] {
            if !visited[v] {
                nts, nte := dfs(v)
                ts = ts || nts
                te = te || nte
            }
        }
        return ts, te
    }
    
    for i := 0; i < n; i++ {
        if !visited[i] {
            ts, te := dfs(i)
            if ts && te {
                return false
            }
        }
    }
    return true
}

Go-specific notes: Go requires explicit slice creation for the graph. Integer overflow is avoided because the constraints fit in 64-bit integers if necessary. Nil slices behave correctly, so no special initialization is needed. DFS is implemented recursively, combining edge-touch flags during backtracking.

Worked Examples

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

Check start/end: neither (0,0) nor (3,4) inside circle. Only one circle exists, it touches neither bottom-left nor top-right edge simultaneously. Therefore, return true.

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

Check start/end: (0,0) is inside the circle (1,1,2), so immediately return false.

Example 3: `xCorner=3, yCorner=3, circles=[[2,1,1],[1,2,1