Check if the Rectangle Corner Is Reachable

Check if the Rectangle Corner Is Reachable - Problem

Array Math Depth-First Search Breadth-First Search Union Find Geometry Hard

You are given two positive integers xCorner and yCorner, and a 2D array circles, where circles[i] = [x_i, y_i, r_i] denotes a circle with center at (x_i, y_i) and radius r_i.

There is a rectangle in the coordinate plane with its bottom left corner at the origin (0, 0) 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
Touches the rectangle only at the two corners

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

Input & Output

Example 1 — No Blocking Path

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

› Output: true

💡 Note: Single circle at (2,1) with radius 1 doesn't block the path from (0,0) to (3,3). We can go around it.

Example 2 — Path Completely Blocked

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

› Output: false

💡 Note: Circle at (1,1) with radius 2 covers both corners (0,0) and (3,3), making any path impossible.

Example 3 — Multiple Small Circles

$ Input: xCorner = 2, yCorner = 2, circles = [[1,0,1],[0,1,1]]

› Output: false

💡 Note: Two circles create a barrier: one blocks right movement from (0,0), other blocks upward movement, preventing any path to (2,2).

Constraints

1 ≤ xCorner, yCorner ≤ 10⁹
0 ≤ circles.length ≤ 1000
circles[i].length == 3
1 ≤ x_i, y_i, r_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Rectangle Setup

Rectangle from (0,0) to (xCorner,yCorner) with circular obstacles

Path Analysis

Check if circles block all possible paths

Result

Return true if any path exists, false if completely blocked

Key Takeaway

🎯 Key Insight: If circles form a continuous barrier connecting opposite boundaries, no path can exist

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to model this as a connectivity problem. Instead of finding paths, we check if circles form a continuous barrier blocking all paths. The Union-Find approach efficiently determines if obstacles connect opposite boundaries. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Boundary Blocking	O(n²)	O(n)	Use Union-Find to check if circles create a barrier blocking all paths
DFS Path Finding	O(xCorner × yCorner)	O(xCorner × yCorner)	Use DFS to explore all possible paths from (0,0) to (xCorner,yCorner)

Union-Find with Boundary Blocking — Algorithm Steps

Create virtual boundary nodes for each side
Connect overlapping circles
Connect circles touching boundaries to boundary nodes
Check if left+bottom boundaries connect to right+top boundaries

Visualization

Tap to expand

Step-by-Step Walkthrough

Circle Groups

Union overlapping circles into connected components

Boundary Connection

Connect circles touching rectangle boundaries

Block Detection

Check if start-side connects to end-side boundaries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_CIRCLES 1000

struct UnionFind {
    int parent[MAX_CIRCLES + 4];
    int rank[MAX_CIRCLES + 4];
    int n;
};

void initUF(struct UnionFind* uf, int n) {
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
}

int findUF(struct UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = findUF(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionUF(struct UnionFind* uf, int x, int y) {
    int px = findUF(uf, x);
    int py = findUF(uf, y);
    if (px == py) return;
    
    if (uf->rank[px] < uf->rank[py]) {
        uf->parent[px] = py;
    } else if (uf->rank[px] > uf->rank[py]) {
        uf->parent[py] = px;
    } else {
        uf->parent[py] = px;
        uf->rank[px]++;
    }
}

struct Circle {
    int x, y, r;
};

bool solution(int xCorner, int yCorner, struct Circle* circles, int n) {
    if (n == 0) return true;
    
    // Check if start or end is blocked
    for (int i = 0; i < n; i++) {
        int x = circles[i].x, y = circles[i].y, r = circles[i].r;
        if ((long long)x*x + (long long)y*y <= (long long)r*r) return false;
        long long dx = xCorner - x, dy = yCorner - y;
        if (dx*dx + dy*dy <= (long long)r*r) return false;
    }
    
    struct UnionFind uf;
    initUF(&uf, n + 4);
    int LEFT = n, BOTTOM = n+1, RIGHT = n+2, TOP = n+3;
    
    // Check circle overlaps
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = circles[i].x, y1 = circles[i].y, r1 = circles[i].r;
            int x2 = circles[j].x, y2 = circles[j].y, r2 = circles[j].r;
            long long dx = x1 - x2, dy = y1 - y2;
            long long sumR = r1 + r2;
            if (dx*dx + dy*dy <= sumR*sumR) {
                unionUF(&uf, i, j);
            }
        }
    }
    
    // Connect circles to boundaries
    for (int i = 0; i < n; i++) {
        int x = circles[i].x, y = circles[i].y, r = circles[i].r;
        if (x <= r) unionUF(&uf, i, LEFT);
        if (xCorner - x <= r) unionUF(&uf, i, RIGHT);
        if (y <= r) unionUF(&uf, i, BOTTOM);
        if (yCorner - y <= r) unionUF(&uf, i, TOP);
    }
    
    // Check if path is blocked
    int leftRoot = findUF(&uf, LEFT);
    if (findUF(&uf, BOTTOM) == leftRoot) {
        if (findUF(&uf, RIGHT) == leftRoot || findUF(&uf, TOP) == leftRoot) {
            return false;
        }
    } else {
        if (findUF(&uf, LEFT) == findUF(&uf, RIGHT) || findUF(&uf, LEFT) == findUF(&uf, TOP) ||
            findUF(&uf, BOTTOM) == findUF(&uf, RIGHT) || findUF(&uf, BOTTOM) == findUF(&uf, TOP)) {
            return false;
        }
    }
    
    return true;
}

int main() {
    int xCorner, yCorner;
    scanf("%d", &xCorner);
    scanf("%d", &yCorner);
    
    char line[10000];
    scanf(" %s", line);
    
    struct Circle circles[MAX_CIRCLES];
    int n = 0;
    
    if (strcmp(line, "[]") == 0) {
        printf(solution(xCorner, yCorner, circles, 0) ? "true\n" : "false\n");
        return 0;
    }
    
    // Parse circles array
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            circles[n].x = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            circles[n].y = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            circles[n].r = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        }
        ptr++;
    }
    
    printf(solution(xCorner, yCorner, circles, n) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Check all pairs of circles for overlap, plus Union-Find operations

⚠ Quadratic Growth

Space Complexity

O(n)

Union-Find data structure stores parent/rank for each circle and boundary

⚡ Linearithmic Space

9.0K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find with Boundary Blocking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler