Q593. Valid Square

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
 

Note:

All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.

There are many ways to solve this problem but I found the solution provided by LeetCode interesting and clever so that I want to write it down here. Before getting into their trick, let me state what I did and what makes this problem a bit challenging.

I ended up calculating all the pairwise distances between all pairs of points. And then, I check if these distances follow what we would expect from a square. In short, we check two things:

• If there is only two values of distances.
• If the smaller distance has 8 instances and the larger one has 4 instance.

If these are correct, we can say it is square. The reason is as follow. Since these smaller distances can only come from the sides A-B, B-C, C-D, D-A. We can check that other cases are impossible. So, it can only be diamond. And the longer distances are all the same value, so the diamond has to be square.

The Python submission.

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        pp = [p1, p2, p3, p4]
        ll = []
        for q1 in pp:
            for q2 in pp:
                if q1 == q2:
                    continue
                ll.append(self.dist(q1, q2))
        if len(ll) < 12:
            return False
        min_l = min(ll)
        max_l = max(ll)
        if min_l == max_l:
            return False
        n_min = 0
        n_max = 0
        for l in ll:
            if l == min_l:
                n_min += 1
            if l == max_l:
                n_max += 1
        if n_min == 8 and n_max == 4:
            return True
        else:
            return False
    def dist(self, s1, s2):
        x1, y1 = s1
        x2, y2 = s2
        return (x1 - x2) ** 2 + (y1 - y2) ** 2

OK, next, let’s talk about the trick I learned on LeetCode solution. When approaching this problem, one of the difficulty is to give the points a good order. If we know the proper ordering of the points (A-B-C-D as square where “-” presents the side), the job is reduced to a simple check, i.e. are these sides equal? And are these diagonals equal?

Following this thought, we can easily come up with a brute force solution where we check each ordering. This is fine since the number of ordering is still $O(1)$.

But actually, we can have a good ordering to begin with. Suppose we indeed have a square, then the order the points by x-axis first and y-axis secondly gives a good ordering to check. So, we can order the points using this strategy and check. If this ordering does not pass the check, we are sure that it is not a square. And if it does pass, it is indeed a square.

The Python submission.

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        pp = [ p1, p2, p3, p4 ]
        pp = sorted(pp)
        d12 = self.dist(pp[0], pp[1])
        d13 = self.dist(pp[0], pp[2])
        if d12 != d13 or d12 == 0:
            return False
        d14 = self.dist(pp[0], pp[3])
        d23 = self.dist(pp[1], pp[2])
        if d23 != d14:
            return False
        return True
    def dist(self, x, y):
        dist = 0
        for i, j in zip(x, y):
            dist += (i - j) ** 2
        return dist