Check Vertical Reflection Symmetry with Duplicate Points

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

Vertical Mirror Symmetry of a Point Multiset

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.

Hints

1. For a nonempty input, ask how many different vertical lines could possibly be valid, and what the extreme points tell you about it.
2. The line may sit at a half-integer; consider working with 2*c so everything stays an integer.
3. Presence is not enough: compare how many times each point and its reflection occur.

Approach

Algorithm: count the multiplicity of every distinct point in a hash map and track the minimum and maximum x-coordinate. For a nonempty input, the only possible line is x = (min_x + max_x) / 2, so work with the doubled axis s = min_x + max_x to stay in integers (this handles half-integer lines). Then for every distinct point (x, y) with count k, check that (s - x, y) also appears exactly k times.

Why the axis is forced: reflection across x = c reverses the order of x-coordinates, so the leftmost occurrence must map to the rightmost one; hence 2c = min_x + max_x. If the check fails for this c, no other line can work.

Correctness: the condition checked is exactly the definition (each pair and its reflection have equal multiplicity). Points with x = c map to themselves, so their count is compared with itself and always matches regardless of parity. Because the check runs over every distinct key, both directions of each pair are verified.

Edge cases: the empty list returns true; a single point, or any input whose points all share one x, is symmetric. Since min_x <= x <= max_x, every reflected x = s - x stays inside [min_x, max_x], but s itself can reach +/-2000000000, so 64-bit arithmetic is used in Java and C++; Java and C++ pack (x, y) into one non-negative 64-bit key.

• Time complexity: O(n)
• Space complexity: O(n)