Clean python solution: hashMap + sort


  • 0
    R

    data structure: hashMap, sortedArray
    algorithm: two pointer

    The KEY of hashMap is the value of Y. The value of each KEY is a sortedArray that saves all points located Y height. Now we simplified the question to check whether each line can be reflected.

    At each line, we start with a midValue, find the diff between (left pointer, midValue) and (midValue, right pointer). If the diff is not equal, the line is not reflected. If the line is reflected, we save the midValue to a set.

    The length of set has to be < 2 because we only want one vertical line.

    class Solution(object):
    
    def lineReflected(self, sortedArr, midValue, i, j):
        lPre = rPre = midValue
        
        while i >= 0:
            l = sortedArr[i]
            r = sortedArr[j]
            
            if lPre - l != r - rPre:
                return False
                
            lPre = l
            rPre = r
            i -= 1
            j += 1
        return True
        
    
    def isReflected(self, points):
        """
        :type points: List[List[int]]
        :rtype: bool
        """
        from collections import defaultdict
        mp = defaultdict(list)
        for point in points:
            mp[point[1]].append(point[0])
        xSet = set([])
        
        for k, v in mp.items():
            v.sort()
            n = len(v)
            if n & 1:
                i = j = n / 2
                midValue = v[n/2]
                xSet.add(midValue)
            else:
                i = n / 2 - 1
                j = n / 2
                midValue = (v[i] + v[j]) / float(2)
                xSet.add(midValue)
                
            if not self.lineReflected(v, midValue, i, j):
                return False
        return len(xSet) <= 1

Log in to reply
 

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