593. Valid Square
Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 43.3%
Problem Breakdown
We are given four points in a 2D plane and need to determine if they form the vertices of a square. The order of the input points is arbitrary, so we cannot assume which point connects to which without checking all geometric relationships.
Key constraints:
- A valid square must have equal side lengths (positive) and right angles.
- Input coordinates are integers between -10^4 and 10^4.
- We need to handle cases where points might overlap or be collinear, which would invalidate the shape as a proper geometric figure with area > 0.
Intuition
A brute-force approach might try checking every permutation of point connections (e.g., p1-p2 is side vs diagonal), but that’s messy and error-prone due to floating-point precision when calculating slopes or angles for right-angle checks.
The key insight relies on the properties of a square regarding distances between vertices:
- A square has 4 sides of equal length () and 2 diagonals of equal length ().
- Since , there will be exactly two unique distance values among all pairs.
- Specifically, the smaller value (side squared) should appear 4 times in our pairwise distances list, and the larger value (diagonal squared) should appear 2 times.
However, we can simplify this check: If a set of points forms a square with non-zero area, calculating the Euclidean distance between all pairs will yield exactly two unique positive values in our frequency map. Any other configuration (rectangle, rhombus, trapezoid) or degenerate case (overlapping points) results in either more than two unique distances or zero-distance entries.
Approach
- Calculate Pairwise Distances: Iterate through all 6 combinations of the 4 input points and compute their squared Euclidean distance: . Using squared distance avoids floating-point errors from
sqrtoperations while keeping calculations in integers. - Filter Valid Distances: Store these distances in a set or frequency map to identify unique values. We must ignore zero-distance pairs, as they indicate overlapping points which are not allowed for a valid square side length > 0.
- Validate Counts: Check if the number of unique positive squared distances is exactly two. This implicitly handles the requirement that sides and diagonals differ in length (which distinguishes squares from rectangles/rhombuses).
Complexity Analysis
- Time Complexity: . Since we always process a fixed set of 4 points, there are always distance calculations. The arithmetic operations and hash map insertions for these constant number of elements take constant time relative to input size (though dependent on coordinate magnitude).
- Space Complexity: . We store at most 6 distances in a set/map, which is bounded by the fixed problem constraints.
Solution
from itertools import combinations
def validSquare(p1, p2, p3, p4):
points = [p1, p2, p3, p4]
# Calculate squared Euclidean distance for all 6 pairs of vertices
distances = []
for i in range(4):
for j in range(i + 1, 4):
x_diff_sq = (points[i][0] - points[j][0]) ** 2
y_diff_sq = (points[i][1] - points[j][1]) ** 2
distances.append(x_diff_sq + y_diff_sq)
# Filter out zero lengths to ensure no overlapping vertices
positive_distances = [d for d in distances if d > 0]
# A valid square must have exactly two unique side/diagonal length values.
# (4 sides equal, 2 diagonals equal -> set size is 2)
return len(set(positive_distances)) == 2
# Example usage:
print(validSquare([0,0], [1,1], [1,0], [0,1])) # True
Edge Cases Handled
- Overlapping Points: The code filters out distances of
0. If any two points are identical (e.g.,[0,0]and[0,0]), the set size check will fail or result in incorrect logic if not filtered. By filtering positive distances only, we ensure side length > 0. - Collinear Points: Collinear points produce distance sets that do not match the
2 unique valuespattern (usually resulting in more than two distinct lengths). - Non-Square Rectangles/Rhombuses: A rectangle with unequal sides produces three unique distances (), so it returns
False. A rhombus that isn’t a square also has unequal diagonals producing 3 unique distance values.