DSA problem
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 input is not guaranteed to be in any particular order, and the square may be rotated at any angle — its sides do not need to be axis-aligned.
The defining property of a square is: four equal sides, four right angles. Equivalently, the four pairwise distances between its corners consist of exactly two distinct values: the side length s appears four times (the four sides) and the diagonal length s * sqrt(2) appears twice (the two diagonals).
Computing six pairwise distances is enough to verify both conditions without worrying about ordering or rotation. We use squared distances to avoid any floating-point error from sqrt: a square of side s has four sides of squared length s^2 and two diagonals of squared length 2 * s^2. So we want exactly two distinct squared distances among the six pairwise values, the smaller appearing four times and the larger appearing twice, with the larger equal to twice the smaller.
We also need to reject degenerate cases. If any two of the four points coincide, the smallest squared distance is zero — the four points then collapse onto a line or a single point and cannot form a square. A short, robust implementation sorts the six squared distances and checks that d[0] == d[1] == d[2] == d[3] > 0, d[4] == d[5], and d[4] == 2 * d[0]. The algorithm runs in O(1) time and O(1) space — there are only six distances regardless of input size.
Examples
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]truep1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]falsep1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]trueConstraints
- pi.length == 2
- -10^4 <= xi, yi <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.