Valid Square
Last Updated: March 28, 2026
Understanding the Problem
We are given exactly four points and need to determine whether they form a valid square. This sounds simple, but there are a few subtleties. The points can come in any order, so we cannot assume which points are adjacent. The square might also be rotated at any angle, not just axis-aligned. And we need to exclude degenerate cases where all four points coincide at the same location (that would give "sides" of length zero).
The core challenge is this: how do we check the square property without knowing which pairs of points form sides versus diagonals? The key observation is that among four points forming a square, there are exactly 6 pairwise distances. If the shape is a valid square, exactly 4 of those distances are equal (the sides) and exactly 2 are equal (the diagonals). The diagonal length is exactly sqrt(2) times the side length. We can use squared distances to avoid floating-point issues entirely.
Key Constraints:
- We always have exactly 4 points -> The input size is fixed and tiny. Any approach from O(1) to O(n!) would work in terms of time. The challenge is correctness, not performance.
-10^4 <= x_i, y_i <= 10^4-> Coordinates fit comfortably in 32-bit integers. Squared distances can be up to (2 10^4)^2 = 4 10^8, which fits in a 32-bit integer but is borderline. Use 64-bit integers for safety.
Approach 1: Check All Permutations
Intuition
The most direct way to check if four points form a square is to try every possible ordering of the points as corners of a quadrilateral, then verify if that ordering produces a valid square. A quadrilateral ABCD is a square if all four sides (AB, BC, CD, DA) are equal and both diagonals (AC, BD) are equal. We also need the side length to be positive (to exclude the degenerate case of four identical points).
We can fix one point (say p1) as the first corner. Then try all 3! = 6 permutations of the remaining three points as the second, third, and fourth corners. For each permutation, check the square property.
Algorithm
- Fix p1 as the first corner.
- Generate all 6 permutations of (p2, p3, p4).
- For each permutation, treat the four points as consecutive corners of a quadrilateral.
- Check if all four sides have equal squared distance and both diagonals have equal squared distance.
- Also verify that the side length is greater than zero.
- If any permutation passes the check, return true. Otherwise, return false.
Example Walkthrough
Code
- Time Complexity: O(1). We try at most 6 permutations, each requiring 6 distance computations. Everything is constant since we always have exactly 4 points.
- Space Complexity: O(1). We only use a fixed number of variables regardless of input.
This approach works correctly, but it feels inelegant. We are generating permutations and checking each one when the ordering of points should not matter. What if we could characterize a valid square purely by the set of pairwise distances?
Approach 2: Sort All Pairwise Distances
Intuition
Here is the key geometric insight. Among 4 points, there are C(4,2) = 6 pairwise distances. For a valid square, 4 of these distances are equal (the sides) and 2 are equal (the diagonals). The diagonal is strictly longer than the side (specifically, diagonal^2 = 2 * side^2). The side length must be positive.
So instead of worrying about point ordering, we can simply compute all 6 squared distances, sort them, and check this pattern. After sorting, the first 4 values should all be the same (sides) and the last 2 should be the same (diagonals).
A square is uniquely characterized by its distance multiset. Among all quadrilaterals, only a square produces exactly two distinct pairwise distances where exactly 4 distances equal the smaller value and exactly 2 distances equal the larger value, with the larger being exactly twice the smaller (in squared terms). A rectangle would have three distinct distance values. A rhombus would have 4 equal sides but two different diagonal lengths. The Pythagorean check (diagonal^2 = 2 * side^2) ensures 90-degree angles, ruling out any non-square shape.
Algorithm
- Compute all 6 pairwise squared distances between the 4 points.
- Sort the 6 distances.
- Check that the first 4 distances are equal (these are the sides).
- Check that the last 2 distances are equal (these are the diagonals).
- Check that the side length is positive (distances[0] > 0).
- Check that diagonal^2 = 2 side^2 (distances[4] = 2 distances[0]).
Example Walkthrough
Code
- Time Complexity: O(1). We compute 6 distances and sort 6 elements. Both operations take constant time since the input is always 4 points.
- Space Complexity: O(1). We store exactly 6 distance values regardless of input.
The sorting approach is clean, but we can avoid sorting entirely by using a frequency map to count distinct distances directly.
Approach 3: Distance Set with Count Validation
Intuition
Instead of sorting, we compute all 6 pairwise squared distances and put them in a frequency map (distance value to count). A valid square must have exactly 2 distinct distance values. The smaller one must appear exactly 4 times (the sides), and the larger one must appear exactly 2 times (the diagonals). We also need the smaller distance to be positive and the larger to equal twice the smaller.
This approach is arguably the most readable version because it directly encodes the geometric property we are checking.
Algorithm
- Compute all 6 pairwise squared distances.
- Store them in a frequency map (distance value -> count).
- Check that there are exactly 2 distinct distance values.
- Let
sidebe the smaller value anddiagbe the larger value. - Check that
sideappears 4 times,diagappears 2 times,side > 0, anddiag == 2 * side.
Example Walkthrough
Code
- Time Complexity: O(1). We compute 6 distances and build a frequency map with at most 6 entries. All constant work.
- Space Complexity: O(1). The frequency map has at most 6 entries. Constant space.