Check Vertical Reflection Symmetry with Duplicate Points
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Determine whether a multiset of two-dimensional points is symmetric about some vertical line. Every occurrence of a point must have a reflected occurrence, including duplicate counts.
### Function Signature
`has_vertical_symmetry(points: list[list[int]]) -> bool`
### Rules
A vertical reflection line has equation `x = c`, where `c` may be an integer or a half-integer. Reflecting `(x, y)` produces `(2*c - x, y)`.
Return true if there exists such a line for which each coordinate pair and its reflection have equal multiplicity in the input. Points on the line reflect to themselves. Input order is irrelevant.
For this exercise, the empty multiset is symmetric and returns true.
### Constraints
- `0 <= len(points) <= 200000`.
- Every point contains exactly two integer coordinates.
- Each coordinate is in `[-1000000000, 1000000000]`.
- Repeated points are allowed and their counts matter.
### Examples
Input: `points = [[1,2],[3,2],[2,4]]`
Output: `true`
The line is `x = 2`.
Input: `points = [[0,1],[1,1]]`
Output: `true`
The line is `x = 0.5`.
Input: `points = [[0,0],[0,0],[2,0]]`
Output: `false`
The left point occurs twice while its reflected point occurs only once.
Input: `points = []`
Output: `true`
Overview: Determine whether a multiset of 2D points is symmetric across a vertical line, preserving duplicate counts and allowing half-integer axes.
Read the full Nuro Software Engineer interview experience this question came from
You are given a multiset of two-dimensional integer points `points`, where each element is `[x, y]`. Determine whether the multiset is symmetric about some vertical line.
A vertical reflection line has equation `x = c`, where `c` may be an integer or a half-integer. Reflecting `(x, y)` across it produces `(2*c - x, y)`.
Return `true` if there exists such a line for which every coordinate pair and its reflection have equal multiplicity in the input. Every occurrence of a point must have a reflected occurrence, so duplicate counts matter. Points on the line reflect to themselves. Input order is irrelevant. The empty multiset is symmetric and returns `true`.
All input coordinates fit in a 32-bit signed integer, and so does the doubled axis `2*c` (the sum of two x-coordinates): it stays within 2000000000 in absolute value, which is still below 2^31 - 1 = 2147483647. The value that does leave 32-bit range is a reflected coordinate `2*c - x`, which can reach 3000000000 in absolute value; use 64-bit arithmetic (Java `long`, C++ `long long`) for these intermediate values.
### Example 1
Input: `points = [[1,2],[3,2],[2,4]]`
Output: `true`
The line is `x = 2`.
### Example 2
Input: `points = [[0,0],[0,0],[2,0]]`
Output: `false`
The left point occurs twice while its reflected point occurs only once.
### Constraints
- `0 <= len(points) <= 200000`
- Every point contains exactly two integer coordinates.
- Each coordinate is in `[-1000000000, 1000000000]`.
- Repeated points are allowed and their counts matter.
Constraints
- 0 <= len(points) <= 200000
- Every point contains exactly two integer coordinates.
- Each coordinate is in [-1000000000, 1000000000].
- Repeated points are allowed and their counts matter.
Examples
Input: ([],)
Expected Output: True
Explanation: The empty multiset is symmetric by definition.
Input: ([[5, -7]],)
Expected Output: True
Explanation: A single point lies on the line x = 5 and reflects to itself.
Hints
- For a nonempty input, ask how many different vertical lines could possibly be valid, and what the extreme points tell you about it.
- The line may sit at a half-integer; consider working with 2*c so everything stays an integer.
- Presence is not enough: compare how many times each point and its reflection occur.