Count Squares Formed by Intersections of Vertical and Horizontal Segments
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a set of vertical line segments and a set of horizontal line segments in the plane. Each segment is described by its start point and end point, and each point is an `(x, y)` pair. Wherever a vertical segment crosses or touches a horizontal segment, their common point is an **intersection point**. Picture a tic-tac-toe grid: two vertical and two horizontal strokes crossing each other enclose a square whose corners are intersection points.
Return the number of squares whose four corners are all intersection points.
The interviewer explained this problem with a drawing. After the basic version, they also asked how to find the segments that cross a given segment faster than by checking every vertical segment against every horizontal one, so be ready to discuss that.
### Function Signature
```python
def count_intersection_squares(vertical: list[list[list[int]]], horizontal: list[list[list[int]]]) -> int:
```
### Rules
- `vertical[i] = [[x1, y1], [x2, y2]]` with `x1 == x2` and `y1 != y2`. `horizontal[j] = [[x1, y1], [x2, y2]]` with `y1 == y2` and `x1 != x2`. The start and end points may be given in either order.
- Segments are closed: their endpoints belong to them, so a segment that ends exactly on another segment still produces an intersection point.
- A point is an intersection point if it lies on at least one vertical segment and at least one horizontal segment.
- Count only axis-aligned squares with positive side length: four corners `(x, y)`, `(x + s, y)`, `(x, y + s)`, `(x + s, y + s)` with `s > 0`, all of which are intersection points. Rectangles that are not squares do not count. Each distinct square is counted once, and squares of every size count, including squares that contain smaller ones.
- Because no two vertical segments share an x-coordinate and no two horizontal segments share a y-coordinate (see Constraints), every counted square has its four sides lying on the given segments.
### Constraints
- `1 <= len(vertical) <= 300`
- `1 <= len(horizontal) <= 300`
- All coordinates are integers in `[-10^6, 10^6]`.
- No two vertical segments have the same x-coordinate, and no two horizontal segments have the same y-coordinate.
- The answer fits comfortably in a 64-bit integer.
### Examples
**Example 1**
- Input: `vertical = [[[1, 0], [1, 3]], [[2, 3], [2, 0]]]`, `horizontal = [[[0, 1], [3, 1]], [[3, 2], [0, 2]]]`
- Output: `1`
- Explanation: The intersection points are `(1, 1)`, `(2, 1)`, `(1, 2)` and `(2, 2)`, the corners of one square of side 1.
**Example 2**
- Input: `vertical = [[[0, 0], [0, 2]], [[1, 0], [1, 2]], [[2, 0], [2, 2]]]`, `horizontal = [[[0, 0], [2, 0]], [[0, 1], [2, 1]], [[0, 2], [2, 2]]]`
- Output: `5`
- Explanation: The nine intersection points form a 3-by-3 grid, which contains four squares of side 1 and one square of side 2.
**Example 3**
- Input: `vertical = [[[0, 0], [0, 4]], [[2, 0], [2, 4]], [[3, 1], [3, 4]]]`, `horizontal = [[[0, 0], [3, 0]], [[0, 2], [3, 2]], [[-1, 3], [3, 3]]]`
- Output: `2`
- Explanation: The vertical segment at `x = 3` starts at `y = 1`, so `(3, 0)` is not an intersection point. The squares are the one with corners `(0, 0)` and `(2, 2)` and the one with corners `(2, 2)` and `(3, 3)`. The side-3 square with corners `(0, 0)` and `(3, 3)` is not counted.
Overview: Given vertical and horizontal line segments defined by start and end points, count the axis-aligned squares whose four corners are all segment intersection points. Tests intersection detection, square enumeration, and faster ways to find which segments cross each other.
You are given a set of vertical line segments and a set of horizontal line segments in the plane. Each segment is described by its two endpoints, and each point is an `(x, y)` pair of integers. Wherever a vertical segment crosses or touches a horizontal segment, their common point is an **intersection point**. Picture a tic-tac-toe grid: two vertical and two horizontal strokes crossing each other enclose a square whose four corners are intersection points.
Implement `count_intersection_squares(vertical, horizontal)` and return the number of squares whose four corners are all intersection points.
### Input
- `vertical[i] = [[x1, y1], [x2, y2]]` with `x1 == x2` and `y1 != y2`.
- `horizontal[j] = [[x1, y1], [x2, y2]]` with `y1 == y2` and `x1 != x2`.
- The two endpoints of a segment may be given in either order.
### Rules
- Segments are **closed**: their endpoints belong to them, so a segment that ends exactly on another segment (a T-junction or a corner touch) still produces an intersection point.
- A point is an intersection point if it lies on at least one vertical segment and at least one horizontal segment.
- Count only axis-aligned squares with positive side length: corners `(x, y)`, `(x + s, y)`, `(x, y + s)`, `(x + s, y + s)` with `s > 0`, all four of which are intersection points. Rectangles that are not squares, and tilted squares, do not count.
- Each distinct square is counted exactly once (not once per corner or orientation), and squares of every size count, including squares that contain smaller ones.
- Because no two vertical segments share an x-coordinate and no two horizontal segments share a y-coordinate, every counted square has its four sides lying on the given segments.
### Output
A single integer: the number of distinct squares. The answer fits in a signed 64-bit integer, so the Java signature returns `long` and the C++ signature returns `long long`. Coordinates, side lengths (at most `2 * 10^6`) and sums such as `y + s` (at most `3 * 10^6` in absolute value) all fit in a 32-bit `int`.
### Example 1
- Input: `vertical = [[[1, 0], [1, 3]], [[2, 3], [2, 0]]]`, `horizontal = [[[0, 1], [3, 1]], [[3, 2], [0, 2]]]`
- Output: `1`
- Explanation: The intersection points are `(1, 1)`, `(2, 1)`, `(1, 2)` and `(2, 2)`, the corners of one square of side 1.
### Example 2
- Input: `vertical = [[[0, 0], [0, 2]], [[1, 0], [1, 2]], [[2, 0], [2, 2]]]`, `horizontal = [[[0, 0], [2, 0]], [[0, 1], [2, 1]], [[0, 2], [2, 2]]]`
- Output: `5`
- Explanation: The nine intersection points form a 3-by-3 grid, which contains four squares of side 1 and one square of side 2.
### Example 3
- Input: `vertical = [[[0, 0], [0, 4]], [[2, 0], [2, 4]], [[3, 1], [3, 4]]]`, `horizontal = [[[0, 0], [3, 0]], [[0, 2], [3, 2]], [[-1, 3], [3, 3]]]`
- Output: `2`
- Explanation: The vertical segment at `x = 3` starts at `y = 1`, so `(3, 0)` is not an intersection point. The squares are the one with corners `(0, 0)` and `(2, 2)` and the one with corners `(2, 2)` and `(3, 3)`. The side-3 square with corners `(0, 0)` and `(3, 3)` is not counted.
### Constraints
- `1 <= len(vertical) <= 300`
- `1 <= len(horizontal) <= 300`
- All coordinates are integers in `[-10^6, 10^6]`.
- No two vertical segments have the same x-coordinate, and no two horizontal segments have the same y-coordinate.
- The answer fits in a signed 64-bit integer.
### Follow-up (discussion only)
After the basic version, the interviewer asked how to find the segments that cross a given segment faster than by checking every vertical segment against every horizontal one. Be ready to discuss that; it is not graded here.
Constraints
- 1 <= len(vertical) <= 300
- 1 <= len(horizontal) <= 300
- All coordinates are integers in [-10^6, 10^6]
- vertical[i] = [[x1, y1], [x2, y2]] with x1 == x2 and y1 != y2; horizontal[j] = [[x1, y1], [x2, y2]] with y1 == y2 and x1 != x2; endpoints may be given in either order
- No two vertical segments have the same x-coordinate, and no two horizontal segments have the same y-coordinate
- The answer fits in a signed 64-bit integer (Java long, C++ long long); side lengths are at most 2 * 10^6 and y + s is at most 3 * 10^6 in absolute value, so coordinates fit in 32-bit int
Examples
Input: ([[[1, 0], [1, 3]], [[2, 3], [2, 0]]], [[[0, 1], [3, 1]], [[3, 2], [0, 2]]])
Expected Output: 1
Input: ([[[0, 0], [0, 2]], [[1, 0], [1, 2]], [[2, 0], [2, 2]]], [[[0, 0], [2, 0]], [[0, 1], [2, 1]], [[0, 2], [2, 2]]])
Expected Output: 5
Hints
- An intersection point is fixed by one vertical and one horizontal segment, and there are at most 300 * 300 such pairs, so you can afford to test every pair. Remember that segments are closed intervals.
- An axis-aligned square is determined by its left and right vertical segments (which fix the side length s) and its bottom row y. Try fixing a pair of vertical segments first.
- For a fixed pair of verticals, look only at the rows both of them meet. You need the rows y for which y + s is also such a row; a hash set or two pointers over sorted y-values finds them in linear time.