Valid Square
Problem
p1..p4 in the plane, each as [x, y],
listed in no particular order. Return true if they are the corners of a
square with a positive side length (the square may be rotated), otherwise
false.p1=[0,0], p2=[1,1], p3=[1,0], p4=[0,1]Outputtruep1=[0,0], p2=[1,1], p3=[1,0], p4=[0,12]Outputfalsep1=[1,0], p2=[-1,0], p3=[0,1], p4=[0,-1]Outputtrueeach point has 2 integer coordinates · -104 ≤ x, y ≤ 104 · the square can be tilted at any angle
Try it yourself
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
}
}
Instinct Digits, factors, slopes or distances hide a formula - find the invariant, then guard against overflow, negatives and floating-point error.
Memory hack Mod peels, gcd reduces, squares compare - and long saves the day. Peel digits with %10, reduce slopes with gcd, compare squared distances.
Open the Math & Geometry guide →Approaches
Brute ForceTry Every Ordering of the Corners
O(1)Space O(1)Since we don't know which corner follows which, try all 4! = 24 orderings
a→b→c→d. An ordering is a square if its four sides share one
positive squared length s and both diagonals equal 2s
(Pythagoras then forces right angles).
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { int[][] pts = {p1, p2, p3, p4}; for (int a = 0; a < 4; a++) for (int b = 0; b < 4; b++) for (int c = 0; c < 4; c++) for (int d = 0; d < 4; d++) { if (a == b || a == c || a == d || b == c || b == d || c == d) continue; if (isSquare(pts[a], pts[b], pts[c], pts[d])) return true; } return false; } // Corners in cycle order a -> b -> c -> d private boolean isSquare(int[] a, int[] b, int[] c, int[] d) { long s = dist(a, b); return s > 0 && dist(b, c) == s && dist(c, d) == s && dist(d, a) == s && dist(a, c) == 2 * s && dist(b, d) == 2 * s; } private long dist(int[] p, int[] q) { long dx = p[0] - q[0], dy = p[1] - q[1]; return dx * dx + dy * dy; }
Constant time but 24 × 6 distance checks and a fiddly permutation loop.
BetterSort the Points to Fix the Cycle
O(1)Space O(1)Sort points by (x, y). For any square, the first and last sorted
points are opposite corners, so the cycle is always
q0→q1→q3→q2. Check those four sides are equal and positive and
that diagonals q0q3 and q1q2 match: an equal-sided shape with
equal diagonals is a square.
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { int[][] q = {p1, p2, p3, p4}; Arrays.sort(q, (u, v) -> u[0] != v[0] ? Integer.compare(u[0], v[0]) : Integer.compare(u[1], v[1])); long side = dist(q[0], q[1]); return side > 0 && dist(q[1], q[3]) == side && dist(q[3], q[2]) == side && dist(q[2], q[0]) == side && dist(q[0], q[3]) == dist(q[1], q[2]); } private long dist(int[] p, int[] q) { long dx = p[0] - q[0], dy = p[1] - q[1]; return dx * dx + dy * dy; }
One fixed ordering instead of 24, but the “sorted order = cycle” claim needs justifying.
OptimalSix Pairwise Distances
O(1)Space O(1)Compute all 6 squared distances and sort them. In a square the 4 smallest are the sides (equal and > 0) and the 2 largest are the diagonals (equal, and twice a side). Order of the input never matters, so no cycle reasoning is required.
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { int[][] p = {p1, p2, p3, p4}; long[] d = new long[6]; int k = 0; for (int i = 0; i < 4; i++) for (int j = i + 1; j < 4; j++) { long dx = p[i][0] - p[j][0], dy = p[i][1] - p[j][1]; d[k++] = dx * dx + dy * dy; } Arrays.sort(d); // 4 equal positive sides, 2 equal diagonals of length^2 = 2 * side^2 return d[0] > 0 && d[0] == d[3] && d[4] == d[5] && d[4] == 2 * d[0]; }
Order-free, branch-light and easy to prove — the cleanest interview answer.
sqrt, no floating-point
equality bugs.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Try Every Ordering of the Corners | O(1) | O(1) |
| Better | Sort the Points to Fix the Cycle | O(1) | O(1) |
| Optimal | Six Pairwise Distances | O(1) | O(1) |
- Allowing zero-length sides — four identical points have all distances equal (0).
- Using
Math.sqrtand comparing doubles — rounding breaks equality. - Assuming the input is in clockwise order — it is not; diagonals may be listed as sides.
- Ask whether the order of points is guaranteed; that is what makes the problem tricky.
- Argue why 4 equal sides + 2 equal diagonals is enough (rhombus with equal diagonals).
- Mention the overflow check: max squared distance here is 8·108; long is safe.