AlgoMaster Logo

Valid Square

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We are given exactly four points and need to determine whether they form a valid square. Three details make this less trivial than it looks. The points can come in any order, so we cannot assume which points are adjacent and which are opposite corners. The square can be rotated at any angle, not only axis-aligned. And we have to reject the degenerate case where points coincide, since four identical points would otherwise pass a naive equal-sides test with sides of length zero.

The central question is how to check the square property without knowing which pairs of points form sides versus diagonals. Among any four points there are exactly 6 pairwise distances. A valid square produces exactly two distinct distance values: 4 of the distances are equal (the sides) and 2 are equal (the diagonals), with the diagonal equal to sqrt(2) times the side. Comparing squared distances instead of actual distances keeps everything in integers and avoids floating-point rounding.

Key Constraints:

  • The input is always 4 points, a fixed size. Time complexity is not a concern here, so every approach below is O(1). The work is in getting correctness right: handling arbitrary ordering, rotation, and degenerate points.
  • -10^4 <= x_i, y_i <= 10^4 means a coordinate difference can reach 2 10^4, so a squared distance can reach (2 10^4)^2 + (2 10^4)^2 = 8 10^8. That fits in a signed 32-bit integer (max about 2.1 * 10^9), so plain int would not overflow here. The solutions below still use 64-bit integers for the distance, which removes any doubt about the intermediate products and costs nothing at this input size.

Approach 1: Check All Permutations

Intuition

If we knew the points in corner order, the check would be straightforward: a quadrilateral ABCD is a square when all four sides (AB, BC, CD, DA) are equal, both diagonals (AC, BD) are equal, and the side length is positive. The positive-length condition excludes the degenerate case of four identical points, which would otherwise have four equal "sides" of length zero.

We do not know the corner order, so we try every order. Fixing p1 as the first corner and permuting the remaining three points gives 3! = 6 candidate orderings. If any ordering satisfies the square check, the points form a square.

Why does equal sides plus equal diagonals force a square, rather than allowing some other shape? A quadrilateral with four equal sides is a rhombus. A rhombus is a square exactly when its diagonals are also equal, because equal diagonals in a rhombus force the interior angles to 90 degrees. So the two conditions together are sufficient.

Algorithm

  1. Fix p1 as the first corner.
  2. Generate all 6 permutations of (p2, p3, p4).
  3. For each permutation, treat the four points as consecutive corners of a quadrilateral.
  4. Check if all four sides have equal squared distance and both diagonals have equal squared distance.
  5. Also verify that the side length is greater than zero.
  6. If any permutation passes the check, return true. Otherwise, return false.

Example Walkthrough

1Try all 6 orderings of p2, p3, p4 with p1 fixed as first corner
0
p1-p2-p3-p4
try
1
p1-p2-p4-p3
2
p1-p3-p2-p4
3
p1-p3-p4-p2
4
p1-p4-p2-p3
5
p1-p4-p3-p2
1/4

Code

Permuting the points works, but the ordering is an artifact of how we set up the check, not part of the problem. The next approach drops ordering entirely and characterizes a square by the multiset of its 6 pairwise distances.

Approach 2: Sort All Pairwise Distances

Intuition

Among 4 points there are C(4,2) = 6 pairwise distances. A valid square has 4 equal sides and 2 equal diagonals, with the diagonal strictly longer than the side (in squared terms, diagonal^2 = 2 * side^2), and a positive side length. None of this depends on which points are adjacent, so we can compute all 6 squared distances, sort them, and test the pattern directly. After sorting, the first 4 values are the sides and the last 2 are the diagonals.

Algorithm

  1. Compute all 6 pairwise squared distances between the 4 points.
  2. Sort the 6 distances.
  3. Check that the first 4 distances are equal (these are the sides).
  4. Check that the last 2 distances are equal (these are the diagonals).
  5. Check that the side length is positive (distances[0] > 0).
  6. Check that diagonal^2 = 2 side^2 (distances[4] = 2 distances[0]).

Example Walkthrough

1Compute 6 pairwise squared distances between 4 points
0
?
1
?
2
?
3
?
4
?
5
?
1/5

Code

The next approach replaces the sort with a frequency map, which counts how many times each distance appears and states the square condition in those terms directly.

Approach 3: Distance Set with Count Validation

Intuition

Instead of sorting, we compute all 6 pairwise squared distances and group them by value in a frequency map. A valid square has exactly 2 distinct distance values: the smaller appears 4 times (the sides) and the larger appears 2 times (the diagonals). The smaller must be positive, and the larger must equal twice the smaller.

The counts read directly off the map, so the code states the square condition (4 sides, 2 diagonals, right angle) without first sorting or indexing into a fixed layout.

Algorithm

  1. Compute all 6 pairwise squared distances.
  2. Store them in a frequency map (distance value -> count).
  3. Check that there are exactly 2 distinct distance values.
  4. Let side be the smaller value and diag be the larger value.
  5. Check that side appears 4 times, diag appears 2 times, side > 0, and diag == 2 * side.

Example Walkthrough

1Compute 6 pairwise squared distances for rotated square
0
?
1
?
2
?
3
?
4
?
5
?
1/4

Code