Line Reflection - Practice Coding Problems

Line Reflection - Problem

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 other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.

Note: There can be repeated points.

Input & Output

Example 1 — Perfect Symmetry

$ Input: points = [[1,1],[-1,1]]

› Output: true

💡 Note: The reflection line is at x = 0. Point (1,1) reflects to (-1,1) and vice versa. Both reflections exist in the original set.

Example 2 — No Symmetry

$ Input: points = [[1,1],[-1,-1]]

› Output: false

💡 Note: The reflection line would be at x = 0. Point (1,1) reflects to (-1,1), but (-1,1) doesn't exist. Point (-1,-1) reflects to (1,-1), but (1,-1) doesn't exist.

Example 3 — Single Point

$ Input: points = [[0,0]]

› Output: true

💡 Note: A single point can always be reflected across a line through itself, so it's symmetric.

Constraints

1 ≤ points.length ≤ 10⁴
-10⁸ ≤ points[i][0], points[i][1] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given set of 2D points on a plane

Find Mirror Line

Calculate center line and test for symmetry

Check Reflections

Verify each point has its mirror image

Key Takeaway

🎯 Key Insight: The reflection line must be at the exact center of min and max x-coordinates

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that if a reflection line exists, it must be at the center of all points' x-coordinates: (min_x + max_x) / 2. The optimal approach calculates this center line and uses a hash set to verify each point has its reflection in O(1) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Center Line Calculation	O(n)	O(n)	Calculate the exact center line position and verify all reflections exist
Brute Force - Try All Possible Lines	O(n³)	O(n)	Test every possible vertical line position to see if it creates perfect symmetry

Hash Map with Center Line Calculation — Algorithm Steps

Find min and max x-coordinates to calculate center line
Store all points in a hash set for O(1) lookup
Check each point has its reflection across the center line

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Center

Calculate center line at (min_x + max_x) / 2

Hash Points

Store all points in hash set for O(1) lookup

Verify Reflections

Check each point has its reflection across center line

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_POINTS 1000

bool solution(int points[][2], int n) {
    if (n <= 1) return true;
    
    int minX = points[0][0];
    int maxX = points[0][0];
    
    for (int i = 0; i < n; i++) {
        if (points[i][0] < minX) minX = points[i][0];
        if (points[i][0] > maxX) maxX = points[i][0];
    }
    
    double lineX = (minX + maxX) / 2.0;
    
    for (int i = 0; i < n; i++) {
        int reflectedX = (int)(2 * lineX - points[i][0]);
        int reflectedY = points[i][1];
        
        bool found = false;
        for (int j = 0; j < n; j++) {
            if (points[j][0] == reflectedX && points[j][1] == reflectedY) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int points[MAX_POINTS][2];
    int n = 0;
    
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') ptr++;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = strtol(ptr, &ptr, 10);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr == ',') ptr++;
            points[n][1] = strtol(ptr, &ptr, 10);
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    printf(solution(points, n) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find min/max, single pass to check reflections

✓ Linear Growth

Space Complexity

O(n)

Hash set stores all n points

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Center Line Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler