Jobs

Interviews

Discussions

Line Reflection

Medium

Nuro

1 view

Topics:

ArraysTwo Pointers

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically, in which case return true; otherwise return false.

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

Constraints:

n == points.length
1 <= n <= 10⁴
points[i].length == 2
-10⁸ <= points[i][0], points[i][1] <= 10⁸

Line Reflection

Medium

Nuro

1 view

Topics:

ArraysTwo Pointers

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically, in which case return true; otherwise return false.

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

Constraints:

n == points.length
1 <= n <= 10⁴
points[i].length == 2
-10⁸ <= points[i][0], points[i][1] <= 10⁸

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the x and y coordinates of the points? Should I assume integers, or can they be floating-point numbers?
Can the input list of points be empty, or can it contain duplicate points?
If multiple lines of reflection exist, is it sufficient to return true if at least one such line exists, or is there a specific line I need to identify?
If the list of points contains only one point, should I consider the line of reflection to exist (returning true), or is this a case where no reflection is possible (returning false)?
For reflection, should I consider approximate equality if using floating-point numbers (using a tolerance), or must the reflection be exact?

Brute Force Solution

Approach

The brute force strategy for determining if points reflect across a vertical line involves checking all possible vertical lines. For each potential line, we verify if every point has a reflected counterpart across that line. This is done by exhaustively checking each point against all other points.

Here's how the algorithm would work step-by-step:

First, find the minimum and maximum x-coordinates among all the points.
Calculate the potential line of reflection by finding the midpoint between the minimum and maximum x-coordinates.
For each point, calculate its expected reflected point across the line.
Check if the reflected point exists in the original set of points.
If even one point doesn't have a corresponding reflected point, the line of reflection is invalid.
If all points have corresponding reflected points, the line of reflection is valid and we have found our solution.

Code Implementation

def is_line_reflection_brute_force(points):
    # If there are no points, there's nothing to reflect.
    if not points:
        return True

    x_coordinates = [point[0] for point in points]
    min_x = min(x_coordinates)
    max_x = max(x_coordinates)

    # Calculate the x-coordinate of the potential reflection line.
    potential_reflection_line = (min_x + max_x) / 2

    points_set = set(tuple(point) for point in points)

    # Iterate through each point to see if its reflection exists.
    for point in points:
        expected_reflection_x = 2 * potential_reflection_line - point[0]
        expected_reflected_point = (expected_reflection_x, point[1])

        # Check if the reflected point is in the original set of points.
        if tuple(expected_reflected_point) not in points_set:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first finds the minimum and maximum x-coordinates which takes O(n) time. Then, for each point (n), the algorithm iterates through all other points (n) to find its reflection. This pair checking operation is nested within the outer loop iterating through all points. Thus, the dominant operation takes approximately n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm needs to check if the reflected point exists in the original set of points. A common way to do this efficiently is to store all the points in a hash set. The space required for the hash set would depend on the number of points, N. Therefore, the space complexity is O(N), where N is the number of points.

Optimal Solution

Approach

To determine if a set of points is symmetric across a vertical line, we can find the potential center line, and then check that each point has a corresponding point on the other side. This avoids trying every possible line by focusing on the potential midpoint implied by the points themselves.

Here's how the algorithm would work step-by-step:

First, find the extreme x-coordinates of all the points. This will help us determine the potential line of symmetry.
Calculate the x-value of the potential vertical line of symmetry by averaging the smallest and largest x-coordinates.
For each point, check if there exists another point that would be its reflection across the calculated line of symmetry. This means the reflected point would be the same distance from the line, but on the opposite side.
If every point has a corresponding reflection, then the points are symmetric across the line. If even one point does not have a reflection, they are not symmetric.

Code Implementation

def is_line_reflection_symmetric(points):
    if not points:
        return True

    min_x = float('inf')
    max_x = float('-inf')

    # Find the minimum and maximum x-coordinates.
    for point_x, point_y in points:
        min_x = min(min_x, point_x)
        max_x = max(max_x, point_x)

    line_of_symmetry = (min_x + max_x) / 2.0
    point_set = set()

    # Use a set for efficient lookup of points.
    for point_x, point_y in points:
        point_set.add((point_x, point_y))

    # Check if each point has a reflection across the line.
    for point_x, point_y in points:

        reflected_x = 2 * line_of_symmetry - point_x

        #If the reflected point isn't present return false.
        if (reflected_x, point_y) not in point_set:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – Finding the minimum and maximum x-coordinates requires iterating through all n points once, which is O(n). The subsequent step of checking for reflections involves iterating through each of the n points. For each point, checking for the existence of its reflection can be efficiently done using a hash set or dictionary, allowing for an average lookup time of O(1). Therefore, checking all n points for their reflections takes O(n) time. The total time complexity is dominated by the sum of these operations, O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm stores all the input points in a set or hash map to efficiently check for reflections. The size of this set depends on the number of input points N, where N is the number of points in the input. Therefore, the space required to store the set of points grows linearly with the number of input points. The space used by other variables like min_x, max_x and line_of_symmetry is constant and does not depend on the input.

Edge Cases

Case	How to Handle
Null or empty points array	Return true since a reflection is trivially possible with no points.
Points array with only one point	Return true, as a single point is always reflected across any line.
Integer overflow when calculating the sum of x-coordinates for finding the reflection line.	Use long data type or check for potential overflow before calculating the sum to prevent incorrect reflection line determination.
Points with very large or very small x-coordinates, potentially leading to precision issues when calculating the reflection line.	Consider using a tolerance when comparing the reflected points to account for potential floating-point inaccuracies, or scale down the coordinates to fit within a manageable range if possible.
Duplicate points in the input array.	Use a set to store the points (x, y) as strings or tuples, handling duplicates automatically and ensuring the reflection check considers unique points only.
All points lie on a single vertical line.	The reflection line is the same vertical line, handle appropriately by making sure to iterate correctly when all x-coordinates are the same.
Maximum number of points leading to memory constraints.	If memory is a concern, consider streaming the input points and processing them in batches, recalculating the reflection line as needed.
Points with identical y-coordinates but different x-coordinates.	The algorithm should correctly handle this case without issues as it relies on comparing x coordinates after reflection across the mid point.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the x and y coordinates of the points? Should I assume integers, or can they be floating-point numbers?
Can the input list of points be empty, or can it contain duplicate points?
If multiple lines of reflection exist, is it sufficient to return true if at least one such line exists, or is there a specific line I need to identify?
If the list of points contains only one point, should I consider the line of reflection to exist (returning true), or is this a case where no reflection is possible (returning false)?
For reflection, should I consider approximate equality if using floating-point numbers (using a tolerance), or must the reflection be exact?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the minimum and maximum x-coordinates among all the points.
Calculate the potential line of reflection by finding the midpoint between the minimum and maximum x-coordinates.
For each point, calculate its expected reflected point across the line.
Check if the reflected point exists in the original set of points.
If even one point doesn't have a corresponding reflected point, the line of reflection is invalid.
If all points have corresponding reflected points, the line of reflection is valid and we have found our solution.

Code Implementation

def is_line_reflection_brute_force(points):
    # If there are no points, there's nothing to reflect.
    if not points:
        return True

    x_coordinates = [point[0] for point in points]
    min_x = min(x_coordinates)
    max_x = max(x_coordinates)

    # Calculate the x-coordinate of the potential reflection line.
    potential_reflection_line = (min_x + max_x) / 2

    points_set = set(tuple(point) for point in points)

    # Iterate through each point to see if its reflection exists.
    for point in points:
        expected_reflection_x = 2 * potential_reflection_line - point[0]
        expected_reflected_point = (expected_reflection_x, point[1])

        # Check if the reflected point is in the original set of points.
        if tuple(expected_reflected_point) not in points_set:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the extreme x-coordinates of all the points. This will help us determine the potential line of symmetry.
Calculate the x-value of the potential vertical line of symmetry by averaging the smallest and largest x-coordinates.
For each point, check if there exists another point that would be its reflection across the calculated line of symmetry. This means the reflected point would be the same distance from the line, but on the opposite side.
If every point has a corresponding reflection, then the points are symmetric across the line. If even one point does not have a reflection, they are not symmetric.

Code Implementation

def is_line_reflection_symmetric(points):
    if not points:
        return True

    min_x = float('inf')
    max_x = float('-inf')

    # Find the minimum and maximum x-coordinates.
    for point_x, point_y in points:
        min_x = min(min_x, point_x)
        max_x = max(max_x, point_x)

    line_of_symmetry = (min_x + max_x) / 2.0
    point_set = set()

    # Use a set for efficient lookup of points.
    for point_x, point_y in points:
        point_set.add((point_x, point_y))

    # Check if each point has a reflection across the line.
    for point_x, point_y in points:

        reflected_x = 2 * line_of_symmetry - point_x

        #If the reflected point isn't present return false.
        if (reflected_x, point_y) not in point_set:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty points array	Return true since a reflection is trivially possible with no points.
Points array with only one point	Return true, as a single point is always reflected across any line.
Integer overflow when calculating the sum of x-coordinates for finding the reflection line.	Use long data type or check for potential overflow before calculating the sum to prevent incorrect reflection line determination.
Points with very large or very small x-coordinates, potentially leading to precision issues when calculating the reflection line.	Consider using a tolerance when comparing the reflected points to account for potential floating-point inaccuracies, or scale down the coordinates to fit within a manageable range if possible.
Duplicate points in the input array.	Use a set to store the points (x, y) as strings or tuples, handling duplicates automatically and ensuring the reflection check considers unique points only.
All points lie on a single vertical line.	The reflection line is the same vertical line, handle appropriately by making sure to iterate correctly when all x-coordinates are the same.
Maximum number of points leading to memory constraints.	If memory is a concern, consider streaming the input points and processing them in batches, recalculating the reflection line as needed.
Points with identical y-coordinates but different x-coordinates.	The algorithm should correctly handle this case without issues as it relies on comparing x coordinates after reflection across the mid point.