Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.
The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Example 1:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] Output: true
Example 2:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] Output: false
Example 3:
Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1] Output: true
Constraints:
p1.length == p2.length == p3.length == p4.length == 2-104 <= xi, yi <= 104To determine whether four given points form a valid square, we rely on geometric properties of squares. A square has four equal sides and two equal diagonals, with the diagonals longer than the sides. Instead of computing square roots, it is more efficient to work with squared Euclidean distances using the formula (x2 - x1)^2 + (y2 - y1)^2.
Compute the distances between all pairs of points (there are six pairs). For a valid square, the four smaller distances should be equal (representing the sides) and the remaining two distances should also be equal (representing the diagonals). Additionally, the side length must be greater than zero to avoid overlapping points.
This approach uses simple math and comparisons, making it straightforward and efficient. Sorting or using a set to analyze the six distances helps confirm whether the required pattern for a square exists.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Compute and compare all pairwise squared distances | O(1) | O(1) |
NeetCode
This approach leverages the property that a square consists of four equal side lengths and two larger equal diagonal lengths. By calculating the distances between every pair of points, sorting these distances, and comparing them, we can validate the square.
Time Complexity: O(1) - The process involves constant time operations for the four points.
Space Complexity: O(1) - We only use a fixed amount of extra space.
1def validSquare(p1, p2, p3, p4):
2 def dist(a, b):
3 return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
4 points = [p1, p2, p3, p4]
5 dists = sorted(dist(points[i], points[j]) for i in range(4) for j in range(i + 1, 4))
6 return 0 < dists[0] == dists[1] == dists[2] == dists[3] and dists[4] == dists[5]This solution defines a helper function dist() to calculate the squared distance between two points, avoiding the cost of computing square roots. It then calculates the distances of all pairs of the four points, sorts them, and checks that the first four distances are equal and positive (indicating the sides of a square) and that the last two distances are equal (indicating the diagonals).
This approach calculates vectors for the sides and diagonals and applies vector dot products to verify perpendicularity (90-degree angles) and equality in length, ensuring all four sides and two diagonals satisfy the square properties.
Time Complexity: O(1) - Fixed operations per four points.
Space Complexity: O(1) - Requires a constant amount of space for storing calculations.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
int dist(const vector<int>& p1, const vector<int>& p2) {
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<int> dists = {dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)};
sort(dists.begin(), dists.end());
return dists[0] > 0 && dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3] && dists[4] == dists[5];
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry and coordinate-based problems like Valid Square can appear in technical interviews at major tech companies. They test mathematical reasoning, careful condition checking, and the ability to translate geometric properties into code.
The optimal approach computes the squared distances between all six pairs of the four points. A valid square will have exactly four equal smaller distances (sides) and two equal larger distances (diagonals). Checking this pattern ensures both equal sides and correct diagonal relationships.
A simple array or list to store the six pairwise squared distances is typically enough. Some solutions also use a set to verify that there are exactly two unique distances corresponding to sides and diagonals.
Squared distances avoid the computational cost of square roots and prevent floating-point precision issues. Since distance comparisons are sufficient for this problem, squared values preserve the same ordering and relationships.
The C++ coverage executes through forming a sequence of distance calculations between every pairwise combination of four points, asserted through vector alignment and consistent square properties for visualized orthogonality.