Problem

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflects the given points.

Examples

Example 1

1
2

Input: [[1,1],[-1,1]]
Output: true

Example 2

1
2

Input: [[1,1],[-1,-1]]
Output: false

Follow up

Could you do better than O(n^2)?

Solution

Method 1 – Hash Set Reflection Check

Intuition

To check if all points are reflected over a vertical line, we note that the reflection line must be at x = (minX + maxX) / 2. For every point (x, y), its reflection is (minX + maxX - x, y). If all such reflected points exist in the set, the answer is true.

Approach

  1. Find the minimum and maximum x-coordinates among all points.
  2. Compute the possible reflection line: x = (minX + maxX) / 2.
  3. Store all points in a set for O(1) lookup.
  4. For each point, check if its reflection across the line also exists in the set.
  5. If all points have their reflections, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
public:
    bool isReflected(vector<vector<int>>& points) {
        int minX = INT_MAX, maxX = INT_MIN;
        unordered_set<string> s;
        for (auto& p : points) {
            minX = min(minX, p[0]);
            maxX = max(maxX, p[0]);
            s.insert(to_string(p[0]) + "," + to_string(p[1]));
        }
        int sum = minX + maxX;
        for (auto& p : points) {
            int rx = sum - p[0];
            string key = to_string(rx) + "," + to_string(p[1]);
            if (!s.count(key)) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import "strconv"
func isReflected(points [][]int) bool {
    minX, maxX := 1<<31-1, -1<<31
    s := make(map[string]struct{})
    for _, p := range points {
        if p[0] < minX { minX = p[0] }
        if p[0] > maxX { maxX = p[0] }
        key := strconv.Itoa(p[0]) + "," + strconv.Itoa(p[1])
        s[key] = struct{}{}
    }
    sum := minX + maxX
    for _, p := range points {
        rx := sum - p[0]
        key := strconv.Itoa(rx) + "," + strconv.Itoa(p[1])
        if _, ok := s[key]; !ok { return false }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        Set<String> set = new HashSet<>();
        for (int[] p : points) {
            min = Math.min(min, p[0]);
            max = Math.max(max, p[0]);
            set.add(p[0] + "," + p[1]);
        }
        int sum = min + max;
        for (int[] p : points) {
            int rx = sum - p[0];
            if (!set.contains(rx + "," + p[1])) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun isReflected(points: Array<IntArray>): Boolean {
        var min = Int.MAX_VALUE; var max = Int.MIN_VALUE
        val set = mutableSetOf<String>()
        for (p in points) {
            min = minOf(min, p[0]); max = maxOf(max, p[0])
            set.add("${p[0]},${p[1]}")
        }
        val sum = min + max
        for (p in points) {
            val rx = sum - p[0]
            if ("$rx,${p[1]}" !in set) return false
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def isReflected(self, points: list[list[int]]) -> bool:
        min_x = min(p[0] for p in points)
        max_x = max(p[0] for p in points)
        s = set((p[0], p[1]) for p in points)
        sum_x = min_x + max_x
        for x, y in points:
            if (sum_x - x, y) not in s:
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

use std::collections::HashSet;
impl Solution {
    pub fn is_reflected(points: Vec<Vec<i32>>) -> bool {
        let min_x = points.iter().map(|p| p[0]).min().unwrap();
        let max_x = points.iter().map(|p| p[0]).max().unwrap();
        let s: HashSet<(i32, i32)> = points.iter().map(|p| (p[0], p[1])).collect();
        let sum = min_x + max_x;
        for p in &points {
            if !s.contains(&(sum - p[0], p[1])) { return false; }
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    isReflected(points: number[][]): boolean {
        let min = Infinity, max = -Infinity;
        const set = new Set<string>();
        for (const [x, y] of points) {
            min = Math.min(min, x);
            max = Math.max(max, x);
            set.add(`${x},${y}`);
        }
        const sum = min + max;
        for (const [x, y] of points) {
            const rx = sum - x;
            if (!set.has(`${rx},${y}`)) return false;
        }
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of points. Each point is processed a constant number of times.
  • 🧺 Space complexity: O(n), for storing all points in a set.