Is Check if the Rectangle Corner Is Reachable easy or hard?

Check if the Rectangle Corner Is Reachable is classified as a Hard problem. It combines geometry, graph traversal, and connectivity reasoning, making it challenging without recognizing the union-find barrier concept.

Check if the Rectangle Corner Is Reachable Python/Java solution

The solution can be implemented in Python, Java, C++, C#, or JavaScript. The BFS method uses a queue to explore reachable grid cells, while the optimized solution uses arrays for Union-Find and distance formulas to detect circle overlaps.

How to solve Check if the Rectangle Corner Is Reachable in O(n^2)?

Use a mathematical approach that checks pairwise circle overlap. If the distance between two circle centers is less than or equal to the sum of their radii, union them in a Disjoint Set. Then verify whether any connected component touches rectangle boundaries in a way that blocks the path from start to destination.

What is the best approach for Check if the Rectangle Corner Is Reachable?

The most efficient solution uses geometric distance checks combined with Union-Find. Circles are treated as nodes, and overlapping circles are grouped into connected components. If a component forms a barrier touching critical rectangle boundaries, it blocks the path. This approach runs in O(n^2) time and O(n) space.

Is Check if the Rectangle Corner Is Reachable asked at Google/Amazon/Meta?

Geometry and graph connectivity problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants that combine BFS, Union-Find, and geometric constraints are especially common in system-level algorithm interviews.

What data structure is used in Check if the Rectangle Corner Is Reachable?

Common data structures include queues for BFS traversal and Disjoint Set Union (Union-Find) for grouping overlapping circles. The optimized approach mainly relies on Union-Find along with mathematical distance calculations.

What is the time complexity of Check if the Rectangle Corner Is Reachable?

The grid BFS approach takes O(W × H) time and space because every grid cell may be visited. The optimized geometric solution compares circle pairs and runs in O(n^2) time with O(n) space using Union-Find.

Description Hints 4 Solution Video 53:28

3235. Check if the Rectangle Corner Is Reachable

Hard24.4% acceptance2 companies

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 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 <= 10⁹
1 <= circles.length <= 1000
circles[i].length == 3
1 <= x_i, y_i, r_i <= 10⁹

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Create a graph with n + 4 vertices.

Hint 2

Vertices 0 to n - 1 represent the circles, vertex n represents upper edge, vertex n + 1 represents right edge, vertex n + 2 represents lower edge, and vertex n + 3 represents left edge.

Hint 3

Add an edge between these vertices if they intersect or touch.

Hint 4

Answer will be false when any of two sides left-right, left-bottom, right-top or top-bottom are reachable using the edges.

53:28

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3235. Check if the Rectangle Corner Is Reachable

Asked at 2 companies

Topics

Hints open one at a time

Similar problems