Easy to understand Python solution


  • 1
    W

    The idea is:

    1. we ignore duplicates in all points with same y values and only save once for duplicates (e.g., for [16,1], [16,1], [16,1], we only save [16,1] once to the dictionary).
    2. we calculate an average x value for all saved points
    3. for all points with same y values, set two pointers (from left and right) to check whether the point pair has the same distance to the average x value.

    '''

    def isReflected(self, points):
    
        if (not points):
            return True
    
        dic = {}
        sumx = 0
        lenwithoutdup = 0
        for point in points:
            if point[1] not in dic:
                dic[point[1]] = {point[0]}
                sumx += point[0]
                lenwithoutdup += 1
            else:
                if point[0] not in dic[point[1]]:
                    dic[point[1]].add(point[0])
                    sumx += point[0]
                    lenwithoutdup += 1
    
        #print sumx, lenwithoutdup
        avgx = float(sumx)/lenwithoutdup
        for item in dic:
            lst = list(dic[item])
            lst.sort()
            i, j = 0, len(lst)-1  # two pointers
            while i <= j:
                #print lst[i], avgx, lst[j]
                if lst[i] - avgx != avgx - lst[j]:
                    return False
                i += 1
                j -= 1
    
        return True

Log in to reply
 

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