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.

Examples

Example 1

1
2

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

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

Example 2

1
2

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

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

Example 3

1
2

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

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

Example 4

1
2

Input: xCorner = 4, yCorner = 4, circles = [[5,5,1]]
Output: true

Explanation:

Constraints

  • 3 <= xCorner, yCorner <= 10^9
  • 1 <= circles.length <= 1000
  • circles[i].length == 3
  • 1 <= xi, yi, ri <= 10^9

Solution

Method 1 – BFS/DFS with Grid Marking

Intuition

We need to find a path from (0,0) to (xCorner, yCorner) inside the rectangle, avoiding all circles. The problem reduces to a grid-based pathfinding problem with forbidden cells (those inside or on any circle). BFS or DFS can be used to explore the grid.

Reasoning

By marking all points that are inside or on any circle as blocked, we can use BFS or DFS to check if there is a path from the bottom-left to the top-right corner. Since the rectangle is small (max 100x100), this approach is efficient.

Approach

  1. Create a grid of size (xCorner+1) x (yCorner+1), initialized as unblocked.
  2. For each cell (x, y), check if it is inside or on any circle. If so, mark it as blocked.
  3. Use BFS or DFS to search for a path from (0,0) to (xCorner, yCorner), only moving to unblocked cells.
  4. Return true if a path exists, otherwise false.

Edge cases:

  • The start or end cell is blocked.
  • No circles: always possible.

Code

 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

class Solution {
public:
    bool isReachable(int xCorner, int yCorner, vector<vector<int>>& circles) {
        int n = xCorner, m = yCorner;
        vector<vector<bool>> blocked(n+1, vector<bool>(m+1, false));
        for (auto& c : circles) {
            int cx = c[0], cy = c[1], r = c[2];
            for (int x = 0; x <= n; ++x) {
                for (int y = 0; y <= m; ++y) {
                    int dx = x - cx, dy = y - cy;
                    if (dx*dx + dy*dy <= r*r) blocked[x][y] = true;
                }
            }
        }
        if (blocked[0][0] || blocked[n][m]) return false;
        queue<pair<int,int>> q;
        q.push({0,0});
        blocked[0][0] = true;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            if (x == n && y == m) return true;
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && !blocked[nx][ny]) {
                    blocked[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return false;
    }
};
 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

func isReachable(xCorner, yCorner int, circles [][]int) bool {
    n, m := xCorner, yCorner
    blocked := make([][]bool, n+1)
    for i := range blocked {
        blocked[i] = make([]bool, m+1)
    }
    for _, c := range circles {
        cx, cy, r := c[0], c[1], c[2]
        for x := 0; x <= n; x++ {
            for y := 0; y <= m; y++ {
                dx, dy := x-cx, y-cy
                if dx*dx+dy*dy <= r*r {
                    blocked[x][y] = true
                }
            }
        }
    }
    if blocked[0][0] || blocked[n][m] {
        return false
    }
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    q := [][2]int{{0,0}}
    blocked[0][0] = true
    for len(q) > 0 {
        x, y := q[0][0], q[0][1]
        q = q[1:]
        if x == n && y == m {
            return true
        }
        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            if nx >= 0 && nx <= n && ny >= 0 && ny <= m && !blocked[nx][ny] {
                blocked[nx][ny] = true
                q = append(q, [2]int{nx, ny})
            }
        }
    }
    return false
}
 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

class Solution {
    public boolean isReachable(int xCorner, int yCorner, int[][] circles) {
        int n = xCorner, m = yCorner;
        boolean[][] blocked = new boolean[n+1][m+1];
        for (int[] c : circles) {
            int cx = c[0], cy = c[1], r = c[2];
            for (int x = 0; x <= n; x++) {
                for (int y = 0; y <= m; y++) {
                    int dx = x - cx, dy = y - cy;
                    if (dx*dx + dy*dy <= r*r) blocked[x][y] = true;
                }
            }
        }
        if (blocked[0][0] || blocked[n][m]) return false;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        blocked[0][0] = true;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            if (x == n && y == m) return true;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx <= n && ny >= 0 && ny <= m && !blocked[nx][ny]) {
                    blocked[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
        return false;
    }
}
 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

class Solution {
    fun isReachable(xCorner: Int, yCorner: Int, circles: Array<IntArray>): Boolean {
        val n = xCorner; val m = yCorner
        val blocked = Array(n+1) { BooleanArray(m+1) }
        for (c in circles) {
            val cx = c[0]; val cy = c[1]; val r = c[2]
            for (x in 0..n) for (y in 0..m) {
                val dx = x - cx; val dy = y - cy
                if (dx*dx + dy*dy <= r*r) blocked[x][y] = true
            }
        }
        if (blocked[0][0] || blocked[n][m]) return false
        val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
        val q = ArrayDeque<Pair<Int,Int>>()
        q.add(0 to 0)
        blocked[0][0] = true
        while (q.isNotEmpty()) {
            val (x, y) = q.removeFirst()
            if (x == n && y == m) return true
            for (d in dirs) {
                val nx = x + d[0]; val ny = y + d[1]
                if (nx in 0..n && ny in 0..m && !blocked[nx][ny]) {
                    blocked[nx][ny] = true
                    q.add(nx to ny)
                }
            }
        }
        return false
    }
}
 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

class Solution:
    def is_reachable(self, xCorner: int, yCorner: int, circles: list[list[int]]) -> bool:
        n, m = xCorner, yCorner
        blocked = [[False]*(m+1) for _ in range(n+1)]
        for cx, cy, r in circles:
            for x in range(n+1):
                for y in range(m+1):
                    if (x-cx)**2 + (y-cy)**2 <= r*r:
                        blocked[x][y] = True
        if blocked[0][0] or blocked[n][m]:
            return False
        from collections import deque
        q = deque([(0,0)])
        blocked[0][0] = True
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]
        while q:
            x, y = q.popleft()
            if x == n and y == m:
                return True
            for dx, dy in dirs:
                nx, ny = x+dx, y+dy
                if 0 <= nx <= n and 0 <= ny <= m and not blocked[nx][ny]:
                    blocked[nx][ny] = True
                    q.append((nx, ny))
        return False
 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

impl Solution {
    pub fn is_reachable(x_corner: i32, y_corner: i32, circles: Vec<Vec<i32>>) -> bool {
        let n = x_corner as usize;
        let m = y_corner as usize;
        let mut blocked = vec![vec![false; m+1]; n+1];
        for c in &circles {
            let (cx, cy, r) = (c[0], c[1], c[2]);
            for x in 0..=n {
                for y in 0..=m {
                    let dx = x as i32 - cx;
                    let dy = y as i32 - cy;
                    if dx*dx + dy*dy <= r*r {
                        blocked[x][y] = true;
                    }
                }
            }
        }
        if blocked[0][0] || blocked[n][m] {
            return false;
        }
        let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
        let mut q = std::collections::VecDeque::new();
        q.push_back((0,0));
        blocked[0][0] = true;
        while let Some((x, y)) = q.pop_front() {
            if x == n && y == m {
                return true;
            }
            for (dx, dy) in dirs.iter() {
                let nx = x as i32 + dx;
                let ny = y as i32 + dy;
                if nx >= 0 && nx <= n as i32 && ny >= 0 && ny <= m as i32 && !blocked[nx as usize][ny as usize] {
                    blocked[nx as usize][ny as usize] = true;
                    q.push_back((nx as usize, ny as usize));
                }
            }
        }
        false
    }
}

Complexity

  • ⏰ Time complexity: O((n*m)*k), where n and m are the rectangle dimensions and k is the number of circles, as we check each cell for each circle and perform BFS/DFS.
  • 🧺 Space complexity: O(n*m), as we store the blocked grid and BFS/DFS queue.