We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Line Reflection

Number: 356

Difficulty: Medium

Paid? Yes

Companies: Yandex, Google, Tinkoff, Adobe

Problem Description

Given n points on a 2D plane, determine if there exists a vertical line (parallel to the y-axis) such that when all points are reflected over this line, the set of reflected points equals the original set of points.

Key Insights

  • The candidate reflection line must be vertical (x = c) and is determined by the average of the minimum and maximum x-coordinates of the points.
  • For each point, its reflected counterpart would have an x-coordinate of 2*c - x while the y-coordinate remains unchanged.
  • A hash set (or similar data structure) can be used to store the points to allow O(1) lookup of the reflected point.
  • Checking every point against its reflection helps decide if the reflection symmetry exists.

Space and Time Complexity

Time Complexity: O(n) - We iterate once to determine min and max, and then once over all points. Space Complexity: O(n) - We store all points in a set for constant time lookup.

Solution

The solution involves first determining the candidate line of reflection by finding the minimum and maximum x-coordinates among all the points and computing their average. This candidate line is given by x = (min_x + max_x) / 2. For each point, we compute its reflected coordinate as (2*candidate - x, y) and verify if this reflected point exists in the set of original points. The use of a hash table (or set) ensures that each lookup is done in constant time, resulting in an overall linear time solution with respect to the number of points.

Code Solutions

# Function to check if a vertical line reflection exists for the given points
def is_reflected(points):
    # If there are no points or a single point, reflection property automatically holds.
    if not points or len(points) == 1:
        return True

    # Initialize the minimum and maximum x values using the first point.
    min_x = max_x = points[0][0]

    # Find the minimum and maximum x-coordinate among all points.
    for x, y in points:
        if x < min_x:
            min_x = x
        if x > max_x:
            max_x = x

    # Calculate candidate reflection line, which is the average of min_x and max_x.
    candidate_line = (min_x + max_x) / 2.0

    # Create a set of tuples for quick lookup of points.
    points_set = set((x, y) for x, y in points)

    # Check each point's reflected counterpart.
    for x, y in points:
        # Calculate the reflected x-coordinate.
        reflected_x = 2 * candidate_line - x
        # Check if the reflected point exists in the set.
        if (reflected_x, y) not in points_set:
            return False
    # All points have valid reflections.
    return True

# Example usage:
print(is_reflected([[1,1],[-1,1]]))  # Expected output: True
print(is_reflected([[1,1],[-1,-1]])) # Expected output: False
← Back to All Questions