How do you solve Check if the Rectangle Corner Is Reachable on LeetCode?

Check if the Rectangle Corner Is Reachable (LeetCode #3235) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The path must avoid all circles while staying within the rectangle.

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

The optimal solution for Check if the Rectangle Corner Is Reachable runs in O(n) time and uses O(n) space. The time complexity is O(n) because we only explore each edge once, and the space complexity is O(n) due to the storage of visited nodes.

What is the brute force solution for Check if the Rectangle Corner Is Reachable?

The brute force approach for Check if the Rectangle Corner Is Reachable is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible path from the bottom left corner to the top right corner. It verifies if any path intersects with the circles, which can be computationally expensive. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Check if the Rectangle Corner Is Reachable?

Always clarify the problem requirements and constraints before jumping into coding. Think about edge cases and how they might affect your solution. Explain your thought process clearly while coding; it helps the interviewer understand your approach.

What are common mistakes when solving Check if the Rectangle Corner Is Reachable?

Failing to account for edge cases where circles touch the rectangle edges. Not considering all possible paths and prematurely returning false.

#3235

Check if the Rectangle Corner Is Reachable

Hard

ArrayMathDepth-First SearchBreadth-First SearchUnion-FindGeometryGraph Traversal (BFS/DFS)Geometry

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of checking every point, we can model the problem as a graph where edges represent possible movements. We can use a BFS or DFS to explore paths while avoiding circles.

⚙️

Algorithm

3 steps

1Step 1: Create a graph with vertices representing the edges of the rectangle and circles.
2Step 2: For each edge, check if it can connect to another edge without intersecting any circles.
3Step 3: Use BFS or DFS to find a path from the bottom left corner to the top right corner.

solution.py21 lines

1from collections import deque
2
3def is_path_reachable(xCorner, yCorner, circles):
4    def can_connect(x1, y1, x2, y2):
5        for cx, cy, r in circles:
6            if (x1 - cx) ** 2 + (y1 - cy) ** 2 < r ** 2 and (x2 - cx) ** 2 + (y2 - cy) ** 2 < r ** 2:
7                return False
8        return True
9
10    queue = deque([(0, 0)])
11    visited = set((0, 0))
12    while queue:
13        x, y = queue.popleft()
14        if x == xCorner and y == yCorner:
15            return True
16        for dx, dy in [(1, 0), (0, 1)]:
17            nx, ny = x + dx, y + dy
18            if 0 <= nx <= xCorner and 0 <= ny <= yCorner and (nx, ny) not in visited and can_connect(x, y, nx, ny):
19                visited.add((nx, ny))
20                queue.append((nx, ny))
21    return False

ℹ

Complexity note: The time complexity is O(n) because we only explore each edge once, and the space complexity is O(n) due to the storage of visited nodes.

1The path must avoid all circles while staying within the rectangle.
2Modeling the problem as a graph allows efficient exploration of possible paths.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.