Scale Engineer

Check if the Rectangle Corner Is Reachable

Hard
#2873Time: 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.
Patterns
MathGeometry
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
Array

Prompt

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:

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:

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:

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

Example 4:

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

Output: true

Explanation:

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem