Problem

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).

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution

Method 1 - Using Constraint on square sides and diagonals

To determine if four points in a 2D space can form a square, we need to verify two main conditions:

  1. Equal Sides: All four sides of the square must be of equal length.
  2. Equal Diagonals: The diagonals must also be of equal length (as this ensures the angles are 90 degrees).

Appraoch

Here is an approach to solve this problem:

  1. Calculate all distances between the points.
  2. Sort these distances: In a valid square, there should be 4 smaller equal distances (sides of the square) and 2 larger equal distances (diagonals).
  3. Check the conditions: If there are 4 equal smaller distances and 2 equal larger distances, the points form a square.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Stream<Integer> distances = Stream.of(
	        distanceSquare(p1, p2), distanceSquare(p1, p3),
            distanceSquare(p1, p4), distanceSquare(p2, p3),
            distanceSquare(p2, p4), distanceSquare(p3, p4)
        );
        Map<Integer, Integer> distanceFreq =
            distances.collect(Collectors.toMap(i
                -> i, // key mapper
                i
                -> 1, // value mapper
                Integer::sum // Merge function to handle dup keys
                ));
        if (distanceFreq.size() != 2) {
            return false;
        }
        // For a valid square, one distance must appear 4 times (sides) and the other 2 times (diagonals)
        int side = Integer.MAX_VALUE, diag = Integer.MIN_VALUE;
        for (int key: distanceFreq.keySet()) {
	        side = Math.min(side, key);
	        diag = Math.max(diag, key);
        }
        
        return distanceFreq.get(side) == 4 || distanceFreq.get(diag) == 2;
    }

    private int distanceSquare(int[] a, int[] b) {
        return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
    }
}

Complexity

  • ⏰ Time complexity: O(1)
    • We calculate the distance between every pair of the four points.
    • There are ( \binom{4}{2} = 6 ) pairs, so this operation involves 6 distance calculations.
    • Each distance calculation involves basic arithmetic operations, which are ( O(1) ).
  • 🧺 Space complexity: O(1)
    • We are just storing 2 values in map OR in worst case 6 values, but it is O(1)