3235. Check if the Rectangle Corner Is Reachable LeetCode Solution
In this guide, you will get 3235. Check if the Rectangle Corner Is Reachable LeetCode Solution with the best time and space complexity. The solution to Check if the Rectangle Corner Is Reachable problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Check if the Rectangle Corner Is Reachable solution in C++
- Check if the Rectangle Corner Is Reachable solution in Java
- Check if the Rectangle Corner Is Reachable solution in Python
- Additional Resources
Problem Statement of Check if the Rectangle Corner Is Reachable
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
Complexity Analysis
- Time Complexity: O(n^2\log^* n)
- Space Complexity: O(n)
3235. Check if the Rectangle Corner Is Reachable LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
bool canReachCorner(int X, int Y, vector<vector<int>>& circles) {
const int n = circles.size();
// Add two virtual nodes, where node n represents (0, 0) and node n + 1
// represents (X, Y).
UnionFind uf(n + 2);
// Iterate through each circle.
for (int i = 0; i < n; ++i) {
const int x = circles[i][0];
const int y = circles[i][1];
const int r = circles[i][2];
// Union the current circle with the node (0, 0) if the circle overlaps
// with the left or top edges.
if (x - r <= 0 || y + r >= Y)
uf.unionByRank(i, n);
// Union the current circle with the node (X, Y) if the circle overlaps
// with the right or bottom edges.
if (x + r >= X || y - r <= 0)
uf.unionByRank(i, n + 1);
// Union the current circle with previous circles if they overlap.
for (int j = 0; j < i; ++j) {
const int x2 = circles[j][0];
const int y2 = circles[j][1];
const int r2 = circles[j][2];
if (static_cast<long>(x - x2) * (x - x2) +
static_cast<long>(y - y2) * (y - y2) <=
static_cast<long>(r + r2) * (r + r2))
uf.unionByRank(i, j);
}
}
// If nodes (0, 0) and (X, Y) are in the same union set, that means there's
// a path of overlapping circles that connects the left or top edges to the
// right or bottom edges, implying that (0, 0) cannot reach (X, Y).
return uf.find(n) != uf.find(n + 1);
}
};
/* code provided by PROGIEZ */3235. Check if the Rectangle Corner Is Reachable LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public boolean canReachCorner(int X, int Y, int[][] circles) {
final int n = circles.length;
// Add two virtual nodes, where node n represents (0, 0) and node n + 1
// represents (X, Y).
UnionFind uf = new UnionFind(n + 2);
// Iterate through each circle.
for (int i = 0; i < n; ++i) {
final int x = circles[i][0];
final int y = circles[i][1];
final int r = circles[i][2];
// Union the current circle with the node (0, 0) if the circle overlaps
// with the left or top edges.
if (x - r <= 0 || y + r >= Y)
uf.unionByRank(i, n);
// Union the current circle with the node (X, Y) if the circle overlaps
// with the right or bottom edges.
if (x + r >= X || y - r <= 0)
uf.unionByRank(i, n + 1);
// Union the current circle with previous circles if they overlap.
for (int j = 0; j < i; j++) {
final int x2 = circles[j][0];
final int y2 = circles[j][1];
final int r2 = circles[j][2];
if ((long) (x - x2) * (x - x2) + (long) (y - y2) * (y - y2) <= (long) (r + r2) * (r + r2))
uf.unionByRank(i, j);
}
}
// If nodes (0, 0) and (X, Y) are in the same union set, that means there's
// a path of overlapping circles that connects the left or top edges to the
// right or bottom edges, implying that (0, 0) cannot reach (X, Y).
return uf.find(n) != uf.find(n + 1);
}
}
// code provided by PROGIEZ3235. Check if the Rectangle Corner Is Reachable LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def canReachCorner(self, X: int, Y: int, circles: list[list[int]]) -> bool:
n = len(circles)
# Add two virtual nodes, where node n represents (0, 0) and node n + 1
# represents (X, Y).
uf = UnionFind(n + 2)
# Iterate through each circle.
for i, (x, y, r) in enumerate(circles):
# Union the current circle with the node (0, 0) if the circle overlaps
# with the left or top edges.
if x - r <= 0 or y + r >= Y:
uf.unionByRank(i, n)
# Union the current circle with the node (X, Y) if the circle overlaps
# with the right or bottom edges.
if x + r >= X or y - r <= 0:
uf.unionByRank(i, n + 1)
# Union the current circle with previous circles if they overlap.
for j in range(i):
x2, y2, r2 = circles[j]
if (x - x2)**2 + (y - y2)**2 <= (r + r2)**2:
uf.unionByRank(i, j)
# If nodes (0, 0) and (X, Y) are in the same union set, that means there's
# a path of overlapping circles that connects the left or top edges to the
# right or bottom edges, implying that (0, 0) cannot reach (X, Y).
return uf.find(n) != uf.find(n + 1)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.