Python solution with detailed comments


  • 0
    G

    Solution

    ** Line Reflection** https://leetcode.com/problems/line-reflection/

    Algorithm

    1. Find the smallest and largest x-value for all points.
    2. If there is a line then it should be at y = (minX + maxX) / 2.
    3. For each point, make sure that it has a reflected point in the opposite side.
    4. How do we find the reflection for a point x? Assume a = (xmin+xmax). Assume reflection of x is xr.
    5. Now (xmin+xmax)/2 = (x+xr)/2 This gives us: xr = xmin+xmax-x
    from collections import defaultdict
    class Solution(object):
        def isReflected(self, points):
            """
            :type points: List[List[int]]
            :rtype: bool
            """
            xmin, xmax, xypoints = float('inf'), float('-inf'), defaultdict(set)
            for point in points:
                x,y = point[0], point[1]
                xypoints[x].add(y)
                xmin, xmax = min(xmin, x), max(xmax, x)
            a = (xmin+xmax)
            for point in points:
                x,y = point[0], point[1]
                if a - x not in xypoints or y not in xypoints[a - x]:
                    return False
            return True
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.