We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if the Rectangle Corner Is Reachable

Number: 3478

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given a rectangle with its bottom‐left corner at (0, 0) and its top‐right corner at (xCorner, yCorner), and a set of circles (each with a center and radius), determine if there exists a continuous path from (0, 0) to (xCorner, yCorner) such that the path remains strictly in the interior of the rectangle (except at the two corners) and never touches or goes inside any circle.

Key Insights

  • The path is allowed only to “touch” the boundary at the two corners; thus no other contact with either the rectangle boundary or any circle is permitted.
  • Each circle defines a forbidden region. If circles—even by “touching” — connect opposing sides of the rectangle (either left with right or top with bottom), they create a barrier that disconnects the two corners.
  • Because the geometry is continuous and the rectangle’s dimensions and circle positions are huge (up to 10^9), a grid exploration is infeasible. Instead, we must solve the problem by testing for a blocking “chain” of circles.
  • We can model each circle as a node and “connect” two circles if they intersect (or touch). In addition, we “mark” each circle that reaches a boundary (using the criterion that a circle touches a boundary if its circle covers that line, i.e. if center – radius <= 0 or center + radius >= rectangle dimension).
  • If any connected component of circles touches both the left and right boundaries or both the top and bottom boundaries (using >= or <= so that even a tangent that is not a mere corner is included), then the forbidden region forms a barrier that prevents a valid path.
  • Otherwise, a path exists.

Space and Time Complexity

Time Complexity: O(n²) in the worst case (n up to 1000, since we check every pair of circles for intersection)
Space Complexity: O(n) for storing union–find structures and boundary markers

Solution

We solve the problem by “union–finding” circles that overlap or touch (using the condition that the Euclidean distance between centers is less than or equal to the sum of their radii). For each circle we also determine whether it “touches” a rectangle boundary. Here the rules are:

  • A circle touches the left boundary if its x-coordinate minus its radius is less than or equal to 0.
  • It touches the right boundary if its x-coordinate plus its radius is greater than or equal to xCorner.
  • Similarly for the bottom (y-coordinate minus radius <= 0) and top (y-coordinate plus radius >= yCorner).

The crux is that a blocking “chain” of circles must “link” two opposite sides of the rectangle. In particular, if some union–find component touches both the left and right boundaries then any interior path (which is not allowed to meet non‐corner boundaries) is blocked vertically; likewise, if a component touches both the top and bottom boundaries the path is blocked horizontally. (Note that a circle that touches a boundary at only a single corner is not “blocking” because the allowed path may touch the corner; hence our “touch” condition uses <= or >= so that even a tangency along an entire arc rather than a mere point is considered.)

Steps:

  1. For each circle, record boolean flags about whether it touches the left, right, bottom, or top boundaries.
  2. Compare every pair of circles. If they intersect (distance between centers ≤ sum of radii), union them.
  3. For each union–find component, merge boundary information from all circles in that set.
  4. If any component has both left and right flags set or both top and bottom flags set, the circles create a barrier and no valid path exists. Otherwise, the path exists.

This approach uses union–find (disjoint sets) to efficiently merge circles and check connectivity among blocked areas.

Code Solutions

# Python solution using union find

import math

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        # track boundary touches for each component: left, right, bottom, top
        self.boundary = [(False, False, False, False) for _ in range(n)]
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            # merge boundary info
            bx1, br1, bb1, bt1 = self.boundary[rootX]
            bx2, br2, bb2, bt2 = self.boundary[rootY]
            newBoundary = (bx1 or bx2, br1 or br2, bb1 or bb2, bt1 or bt2)
            self.parent[rootY] = rootX
            self.boundary[rootX] = newBoundary

def isBlocking(xCorner, yCorner, circles):
    n = len(circles)
    uf = UnionFind(n)
    
    # Precompute boundary contacts for each circle.
    for i, (x, y, r) in enumerate(circles):
        touches_left = (x - r) <= 0
        touches_right = (x + r) >= xCorner
        touches_bottom = (y - r) <= 0
        touches_top = (y + r) >= yCorner
        uf.boundary[i] = (touches_left, touches_right, touches_bottom, touches_top)
    
    # Union circles that intersect or touch
    for i in range(n):
        x1, y1, r1 = circles[i]
        for j in range(i+1, n):
            x2, y2, r2 = circles[j]
            dx = x1 - x2
            dy = y1 - y2
            # if circles intersect or touch
            if dx*dx + dy*dy <= (r1 + r2)**2:
                uf.union(i, j)
    
    # Check each component for blocking barrier:
    for i in range(n):
        root = uf.find(i)
        left, right, bottom, top = uf.boundary[root]
        # if a single component touches both left and right boundaries 
        # or both top and bottom boundaries, a barrier is formed.
        if left and right:
            return True
        if top and bottom:
            return True
    return False

def rectangleCornerReachable(xCorner, yCorner, circles):
    # if some union of circles create a barrier, then no path exists.
    if isBlocking(xCorner, yCorner, circles):
        return False
    return True

# Example usage:
print(rectangleCornerReachable(3, 4, [[2,1,1]]))      # Expected output: True
print(rectangleCornerReachable(3, 3, [[1,1,2]]))      # Expected output: False
print(rectangleCornerReachable(3, 3, [[2,1,1],[1,2,1]]))# Expected output: False
print(rectangleCornerReachable(4, 4, [[5,5,1]]))      # Expected output: True
← Back to All Questions