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.
1var validSquare = function(p1, p2, p3, p4) {
2 function dist(a, b) {
3 return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
4 }
5 let points = [p1, p2, p3, p4];
6 let dists = [];
7 for (let i = 0; i < 4; i++) {
8 for (let j = i + 1; j < 4; j++) {
9 dists.push(dist(points[i], points[j]));
10 }
11 }
12 dists.sort((a, b) => a - b);
13 return dists[0] > 0 && dists[0] === dists[1] && dists[1] === dists[2] && dists[2] === dists[3] && dists[4] === dists[5];
14};The JavaScript implementation follows the same logic as the Python solution. It uses a nested loop to calculate all six distances, pushes these into an array, and sorts the array. The final condition checks ensure the properties of a square.
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.
1class Solution {
2 private int dist
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 Java solution leverages calculating distances in a manner similar to norms of vectors, utilizing sorted indices to verify required conditions for sides and diagonals. This logic maintains computational simplicity while ensuring perfect geometric conditions for a square.