Valid Square
Medium · Math & Geometry · Explanation and code example
Six Squared Distances
How it works
For four distinct points to form a square, their six pair distances consist of four equal nonzero sides and two equal diagonals twice the squared side length. Compute and sort squared distances to check these counts without depending on the input point order.
Steps
- Compute all six squared pair distances.
- Sort them.
- Check four equal positive sides and two equal diagonals of twice that size.
Complexity
- Time: O(1) for four points.
- Space: O(1).
Things to watch for
- A duplicate point creates a zero side and must fail.
- Equal sides alone could describe a rhombus; validate diagonals too.
- Avoid floating-point square roots.
Python code example
from itertools import combinations
class Solution:
def validSquare(self, p1, p2, p3, p4) -> bool:
distances = sorted((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
for a, b in combinations((p1, p2, p3, p4), 2))
return (distances[0] > 0 and
distances[0] == distances[1] == distances[2] == distances[3] and
distances[4] == distances[5] == 2 * distances[0])
C++ code example
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<vector<int>> points{p1, p2, p3, p4};
vector<long long> distances;
for (int i = 0; i < 4; ++i)
for (int j = i + 1; j < 4; ++j) {
long long dx = points[i][0] - points[j][0];
long long dy = points[i][1] - points[j][1];
distances.push_back(dx * dx + dy * dy);
}
sort(distances.begin(), distances.end());
return distances[0] > 0 && distances[0] == distances[1] &&
distances[0] == distances[2] && distances[0] == distances[3] &&
distances[4] == distances[5] && distances[4] == 2 * distances[0];
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.