Valid Square

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

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

Constraints:

• p1.length == p2.length == p3.length == p4.length == 2
• -104 <= xi, yi <= 104

Approach: Distances Set (Distance Characterization)

Algorithm

1. Compute the squared distance between every pair of the four points, for a total of 6 distances
2. In a square these 6 distances take exactly two values: the four equal side lengths and the two equal diagonals, with the diagonal squared being exactly twice the side squared
3. Store all 6 squared distances in a set
4. Return true if and only if the set has exactly 2 distinct values and neither value is zero
5. The non-zero check rules out duplicated points, which cannot form a square

Time & Space Complexity

• Time Complexity: O(1) - only 6 distance computations and set insertions
• Space Complexity: O(1) - the set holds at most 6 values

Java Implementation

import java.util.HashSet;
import java.util.Set;

public class ValidSquare {

    public static boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> distances = new HashSet<>();
        distances.add(distanceSquared(p1, p2));
        distances.add(distanceSquared(p1, p3));
        distances.add(distanceSquared(p1, p4));
        distances.add(distanceSquared(p2, p3));
        distances.add(distanceSquared(p2, p4));
        distances.add(distanceSquared(p3, p4));

        return !distances.contains(0) && distances.size() == 2;
    }

    private static int distanceSquared(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];
        return dx * dx + dy * dy;
    }

    // Test method
    public static void main(String[] args) {
        System.out.println(validSquare(
                new int[]{0, 0}, new int[]{1, 1}, new int[]{1, 0}, new int[]{0, 1})); // Expected: true
        System.out.println(validSquare(
                new int[]{0, 0}, new int[]{1, 1}, new int[]{1, 0}, new int[]{0, 12})); // Expected: false
        System.out.println(validSquare(
                new int[]{1, 0}, new int[]{-1, 0}, new int[]{0, 1}, new int[]{0, -1})); // Expected: true
    }
}

Example Walkthrough

For p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]:

1. Pairwise squared distances: all four sides are 1, and both diagonals are 2
2. The set becomes {1, 2}, which has exactly 2 distinct positive values
3. distances.size() == 2 and no zero: return true

For p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]:

1. Distances: {1, 2, 1, 1, 146, 145} which has more than 2 distinct values
2. Return false

Key Points

1. No Ordering Needed: Using the distance multiset avoids sorting or determining the order of the points
2. Squared Distances: Comparing squared distances avoids floating-point sqrt
3. Two-Value Property: Four equal sides plus two equal diagonals uniquely characterize a square
4. Zero Guard: A zero distance means two points coincide, which can never form a square
5. O(1): With a fixed number of points the solution runs in constant time