Sponsored
Sponsored
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 {
6 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];
}
};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.