Radar Overlaps and Undetected Crossing of a Rectangular Room
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Radars are installed inside a rectangular room bounded by four walls: the left wall `x = 0`, the right wall `x = width`, the bottom wall `y = 0` and the top wall `y = height`. Radar `i` sits at the integer point `(x_i, y_i)` inside the room and detects everything within distance `r_i` of that point, the boundary included.
The interview asked two questions about this setup, and your function answers both:
1. For every radar, which other radars overlap it?
2. Can an object travel from the left wall to the right wall without ever being detected?
### Function Signature
```python
def analyze_radars(width: int, height: int, radars: list[list[int]]) -> tuple[list[list[int]], bool]:
```
`radars[i] = [x_i, y_i, r_i]`. Return the pair `(overlaps, can_cross)`.
### Rules
- The coverage of radar `i` is the closed disk of points `(x, y)` with `(x - x_i)^2 + (y - y_i)^2 <= r_i^2`.
- Radars `i` and `j` (with `i != j`) overlap when their coverage disks share at least one point, that is, when `(x_i - x_j)^2 + (y_i - y_j)^2 <= (r_i + r_j)^2`. Disks that touch at a single point overlap.
- `overlaps` has one list per radar, in input order. `overlaps[i]` contains every index `j` of a radar that overlaps radar `i`, in increasing order, and is empty if there is none.
- The object is a point. It may start at any point of the left wall (`x = 0`, `0 <= y <= height`), follow any continuous path that stays inside the closed rectangle (the walls included), and end at any point of the right wall (`x = width`). It is detected if any point of its path, including the start and end points, lies in the coverage of some radar.
- `can_cross` is `True` if at least one path avoids the coverage of every radar, and `False` otherwise.
- Coverage may extend beyond the walls; only the part inside the room affects the object.
- With no radars, the result is `([], True)`.
### Constraints
- `1 <= width <= 10^6` and `1 <= height <= 10^6`.
- `0 <= len(radars) <= 1000`.
- For every radar: `0 <= x_i <= width`, `0 <= y_i <= height`, and `1 <= r_i <= 10^6`. All values are integers.
- Several radars may share a center, or even be identical; identical radars overlap each other.
- Squared distances and squared radius sums reach about `4 * 10^12`, beyond `2^31 - 1`, so use 64-bit integer arithmetic. All values stay well within `2^53`.
### Examples
**Example 1**
```text
Input: width = 10, height = 6, radars = [[2, 1, 2], [4, 3, 2], [5, 5, 1], [9, 1, 1]]
Output: ([[1], [0, 2], [1], []], False)
```
Radars 0 and 1 overlap (squared distance `8 <= 16`), and radars 1 and 2 overlap (`5 <= 9`); no other pair does. Radar 0 reaches below the bottom wall, radar 2 touches the top wall at `(5, 6)`, and together radars 0, 1 and 2 cover an unbroken band from the bottom wall to the top wall, so the object cannot get past them.
**Example 2**
```text
Input: width = 8, height = 6, radars = [[2, 1, 1], [3, 2, 1], [6, 5, 2]]
Output: ([[1], [0], []], True)
```
Radars 0 and 1 overlap (`2 <= 4`). Radar 2 overlaps neither radar 1 (`18 > 9`) nor radar 0 (`32 > 9`). The straight segments `(0, 3.5) -> (4, 3.5) -> (5, 1) -> (8, 1)` stay outside every radar's coverage.
**Example 3**
```text
Input: width = 10, height = 6, radars = [[2, 2, 2], [6, 2, 2], [6, 5, 1]]
Output: ([[1], [0, 2], [1]], False)
```
Radars 0 and 1 touch at `(4, 2)` (`16 <= 16`) and radars 1 and 2 touch at `(6, 4)` (`9 <= 9`). Radar 0 touches the bottom wall at `(2, 0)` and radar 2 touches the top wall at `(6, 6)`. Touching points are detected, so there is no gap the object could slip through.
Overview: Two-part geometry coding problem about circular radars placed inside a rectangular room. For each radar, list every other radar whose coverage overlaps it, then decide whether a point object can travel from the left wall to the right wall without entering any radar's coverage.
Read the full Snapchat Software Engineer interview experience this question came from
Radars are installed inside a rectangular room bounded by four walls: the left wall `x = 0`, the right wall `x = width`, the bottom wall `y = 0` and the top wall `y = height`. Radar `i` sits at the integer point `(x_i, y_i)` inside the room and detects everything within distance `r_i` of that point, the boundary included.
Implement `analyze_radars(width, height, radars)`, where `radars[i] = [x_i, y_i, r_i]`. It answers two questions about this setup and returns the pair `(overlaps, can_cross)`:
1. For every radar, which other radars overlap it?
2. Can an object travel from the left wall to the right wall without ever being detected?
### Rules
- The coverage of radar `i` is the closed disk of points `(x, y)` with `(x - x_i)^2 + (y - y_i)^2 <= r_i^2`.
- Radars `i` and `j` (with `i != j`) overlap when their coverage disks share at least one point, that is, when `(x_i - x_j)^2 + (y_i - y_j)^2 <= (r_i + r_j)^2`. Disks that touch at a single point overlap.
- `overlaps` has one list per radar, in input order. `overlaps[i]` contains every index `j` of a radar that overlaps radar `i`, in increasing order, and is empty if there is none.
- The object is a point. It may start at any point of the left wall (`x = 0`, `0 <= y <= height`), follow any continuous path that stays inside the closed rectangle (the walls included), and end at any point of the right wall (`x = width`). It is detected if any point of its path, including the start and end points, lies in the coverage of some radar.
- `can_cross` is `True` if at least one path avoids the coverage of every radar, and `False` otherwise.
- Coverage may extend beyond the walls; only the part inside the room affects the object.
- With no radars, the result is `([], True)`.
### Return value
- Python: the tuple `(overlaps, can_cross)`.
- JavaScript: the two-element array `[overlaps, can_cross]`.
- Java: a two-element `java.util.List<Object>` holding `overlaps` (a `java.util.List<java.util.List<Integer>>`) followed by `can_cross` (a `Boolean`).
- C++: a `std::pair<std::vector<std::vector<int>>, bool>` holding `overlaps` and `can_cross`.
### Example 1
```text
Input: width = 10, height = 6, radars = [[2, 1, 2], [4, 3, 2], [5, 5, 1], [9, 1, 1]]
Output: ([[1], [0, 2], [1], []], False)
```
Radars 0 and 1 overlap (squared distance `8 <= 16`), and radars 1 and 2 overlap (`5 <= 9`); no other pair does. Radar 0 reaches below the bottom wall, radar 2 touches the top wall at `(5, 6)`, and together radars 0, 1 and 2 cover an unbroken band from the bottom wall to the top wall, so the object cannot get past them.
### Example 2
```text
Input: width = 8, height = 6, radars = [[2, 1, 1], [3, 2, 1], [6, 5, 2]]
Output: ([[1], [0], []], True)
```
Radars 0 and 1 overlap (`2 <= 4`). Radar 2 overlaps neither radar 1 (`18 > 9`) nor radar 0 (`32 > 9`). The straight segments `(0, 3.5) -> (4, 3.5) -> (5, 1) -> (8, 1)` stay outside every radar's coverage.
### Constraints
- `1 <= width <= 10^6` and `1 <= height <= 10^6`.
- `0 <= len(radars) <= 1000`.
- For every radar: `0 <= x_i <= width`, `0 <= y_i <= height`, and `1 <= r_i <= 10^6`. All values are integers.
- Several radars may share a center, or even be identical; identical radars overlap each other.
- Squared distances and squared radius sums reach about `4 * 10^12`, beyond `2^31 - 1`, so use 64-bit integer arithmetic (`long` in Java, `long long` in C++). All values stay well within `2^53`, so JavaScript numbers remain exact.
Constraints
- 1 <= width <= 10^6 and 1 <= height <= 10^6.
- 0 <= len(radars) <= 1000.
- For every radar: 0 <= x_i <= width, 0 <= y_i <= height, and 1 <= r_i <= 10^6. All values are integers.
- Several radars may share a center, or even be identical; identical radars overlap each other.
- Squared distances and squared radius sums reach about 4 * 10^12, beyond 2^31 - 1, so use 64-bit integer arithmetic (long in Java, long long in C++). All values stay well within 2^53.
Examples
Input: (5, 5, [])
Expected Output: ([], True)
Explanation: No radars: overlaps is empty and the room is freely crossable.
Input: (1, 1, [[0, 0, 1]])
Expected Output: ([[]], False)
Explanation: Smallest room (width = height = 1) with one radar centered on corner (0, 0); its coverage extends beyond the walls and reaches both the bottom (0 - 1 <= 0) and the top (0 + 1 >= 1), so it blocks alone.
Hints
- Every geometric test here can stay in integers: compare squared distances with squared radius sums, remember that touching (equality) counts, and note that these squares exceed the 32-bit range.
- Because every center lies inside the room, whether a radar reaches the bottom or the top wall depends only on y_i, r_i and height.
- Ask what a group of radars would have to look like to stop every left-to-right path: which walls must such a group touch, and how must its members be linked?