Teaching Kids Programming – Valid Square Algorithm by Four Points in Cartesian Coordinate System

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.

The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.

A valid square has four equal sides with positive length and four equal angles (90-degree angles).

four-points-square

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

Example 2:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: false

Example 3:
Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
Output: true

Valid Square Algorithm by Four Points in Cartesian Coordinate System

In a Cartesian Coordinate System, the distance (length) between two Pointers (x1, y1) and (x2, y2) can be computed as follows:

As the points are given in any order, if we compute the distances between every two pairs of points, we should have only two kinds of values for a valid square – four edges are equal and two diagonals are equal length.

However, there is a case that three points are the same and hence the distance between them is zero, so we have to rule of this case.

The algorithm to check whether four points in 2D space can make a valid square is given as follows where we brute force all pairs of points and compute the distance. We then check if there are only two kinds of values – also we have to exclude the scenario mentioned above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        arr = (p1, p2, p3, p4)
        seen = defaultdict(int)
        
        def dist(a, b):
            return sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)
        
        for i in range(4):
            for j in range(i):
                d = dist(arr[i], arr[j])
                seen[d] += 1
        
        return len(seen) == 2 and seen[0] == 0

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        arr = (p1, p2, p3, p4)
        seen = defaultdict(int)
        
        def dist(a, b):
            return sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)
        
        for i in range(4):
            for j in range(i):
                d = dist(arr[i], arr[j])
                seen[d] += 1
        
        return len(seen) == 2 and seen[0] == 0

The time/space complexity is O(1) constant. There are only four points and it takes constant time to compute the distances among them. The space is constant as well as the outcomes have a upper bound.

See also: How to Check If Four Points can Make a Valid Square (C++ and Java)?

–EOF (The Ultimate Computing & Technology Blog) —