Code Implementation

class Solution:
    def validSquare(self, p1, p2, p3, p4):
        def dist2(a, b):
            return (a[0]-b[0])**2 + (a[1]-b[1])**2
        points = [p1, p2, p3, p4]
        dists = []
        for i in range(4):
            for j in range(i+1, 4):
                dists.append(dist2(points[i], points[j]))
        dists.sort()
        return dists[0] > 0 and dists[0] == dists[1] == dists[2] == dists[3] and dists[4] == dists[5] and dists[4] == 2*dists[0]
      

class Solution {
public:
    int dist2(vector<int>& a, vector<int>& b) {
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        vector<vector<int>> points = {p1, p2, p3, p4};
        vector<int> dists;
        for (int i = 0; i < 4; ++i)
            for (int j = i+1; j < 4; ++j)
                dists.push_back(dist2(points[i], points[j]));
        sort(dists.begin(), dists.end());
        return dists[0] > 0 && dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3]
            && dists[4] == dists[5] && dists[4] == 2*dists[0];
    }
};
      

class Solution {
    private int dist2(int[] a, int[] b) {
        return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
    }
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[][] points = {p1, p2, p3, p4};
        int[] dists = new int[6];
        int idx = 0;
        for (int i = 0; i < 4; ++i)
            for (int j = i+1; j < 4; ++j)
                dists[idx++] = dist2(points[i], points[j]);
        Arrays.sort(dists);
        return dists[0] > 0 && dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3]
            && dists[4] == dists[5] && dists[4] == 2*dists[0];
    }
}
      

var validSquare = function(p1, p2, p3, p4) {
    function dist2(a, b) {
        return (a[0]-b[0])**2 + (a[1]-b[1])**2;
    }
    let points = [p1, p2, p3, p4];
    let dists = [];
    for (let i = 0; i < 4; ++i)
        for (let j = i+1; j < 4; ++j)
            dists.push(dist2(points[i], points[j]));
    dists.sort((a, b) => a-b);
    return dists[0] > 0 && dists[0] === dists[1] && dists[1] === dists[2] && dists[2] === dists[3]
        && dists[4] === dists[5] && dists[4] === 2*dists[0];
};
      

Problem Description

You are given four points in a 2D plane, each represented as an array or tuple of two integers: p1, p2, p3, and p4. Your task is to determine if these four points form a valid square.

• All four sides of the square must have the same length.
• All four angles must be right angles (90 degrees).
• The input points may be given in any order.
• Each point must be used exactly once; do not reuse elements.
• Return true if the points form a valid square, and false otherwise.

Thought Process

At first glance, the problem seems to require checking all possible arrangements of the points to see if they form a square. We might consider calculating all distances between pairs of points and then checking for the properties of a square: four equal sides and two equal (longer) diagonals.

A brute-force approach could involve trying all permutations of the points and checking the sides and angles, but this is inefficient. Instead, we can use the fact that, for any set of four points forming a square:

• There are exactly two unique distances among all pairs of points: the side and the diagonal.
• The four sides are equal, and the two diagonals are equal and longer than the sides.
• There are 6 unique pairs of points (since 4 choose 2 = 6).

By calculating all six pairwise distances and analyzing their counts, we can efficiently determine if the points form a square without checking every permutation.

Solution Approach

• Step 1: Store the four points in a list or array for easier access.
• Step 2: Compute the squared distance between every pair of points (6 pairs in total). Squared distance is used to avoid floating-point errors from square roots.
• Step 3: Sort the list of distances. In a valid square:
  • The four smallest distances should be equal (the sides).
  • The two largest distances should be equal (the diagonals), and each diagonal should be exactly twice the side squared (by the Pythagorean theorem).
  • None of the side lengths should be zero (i.e., all points must be distinct).
• Step 4: Check these properties:
  • The first four distances are equal and non-zero.
  • The last two distances are equal.
  • The diagonal distance is exactly twice the side squared.
• Step 5: If all checks pass, return true; otherwise, return false.

This approach is efficient because it leverages the mathematical properties of a square and requires only a constant amount of computation.

Example Walkthrough

Let's consider the following points:

• p1 = [0, 0]
• p2 = [1, 1]
• p3 = [1, 0]
• p4 = [0, 1]

Step 1: Compute all pairwise squared distances:

• Between (0,0)-(1,1): (1-0)^2 + (1-0)^2 = 1+1 = 2
• Between (0,0)-(1,0): (1-0)^2 + (0-0)^2 = 1+0 = 1
• Between (0,0)-(0,1): (0-0)^2 + (1-0)^2 = 0+1 = 1
• Between (1,1)-(1,0): (1-1)^2 + (0-1)^2 = 0+1 = 1
• Between (1,1)-(0,1): (0-1)^2 + (1-1)^2 = 1+0 = 1
• Between (1,0)-(0,1): (0-1)^2 + (1-0)^2 = 1+1 = 2

Step 2: Sort the distances: [1, 1, 1, 1, 2, 2]

Step 3: Check the properties:

• First four are equal and non-zero: 1, 1, 1, 1
• Last two are equal: 2, 2
• Diagonal is twice the side: 2 == 2*1

Time and Space Complexity

Brute-force approach: Trying all permutations of the points and checking sides and angles is O(1) in practice because there are only 4 points (so 24 permutations), but it's unnecessarily complex.

Optimized approach (as above):

• Computing all pairwise distances: 6 pairs, each O(1) = O(1)
• Sorting 6 values: O(1)
• Final checks: O(1)
• Total Time Complexity: O(1) (constant time, since the input size is fixed)
• Space Complexity: O(1) (only a few variables for distances)

Summary

The key insight is that any four points forming a square will have exactly two unique distances among all their pairs: the side and the diagonal. By calculating and sorting all six pairwise squared distances, we can quickly verify if the points form a valid square. This approach is both mathematically elegant and computationally efficient, requiring only a constant number of operations, and avoids the pitfalls of brute-force permutation checking.