Valid Square
MedPrompt
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: trueExample 2:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: falseExample 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 <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is based on the idea that since the order of the input points is not guaranteed, we can try all possible configurations of a square. A quadrilateral is defined by the cyclic order of its vertices. For four points, there are three distinct ways to form a quadrilateral, depending on which point is chosen to be diagonally opposite to a fixed point (say, p1). We can check each of these three configurations to see if it forms a valid square.
Algorithm
- Define a helper function
distSq(a, b)to compute the squared distance between two points. - Define a helper function
isSquare(p1, p2, p3, p4)that checks if the points form a square in the given cyclic order. - Inside
isSquare, calculate the squared lengths of the four sides:distSq(p1, p2),distSq(p2, p3),distSq(p3, p4),distSq(p4, p1). - Calculate the squared lengths of the two diagonals:
distSq(p1, p3)anddistSq(p2, p4). - Return
trueif all four side lengths are equal and positive, and the two diagonal lengths are equal. - In the main function, call
isSquarefor the three possible cyclic orderings of the four points:(p1, p2, p3, p4),(p1, p3, p2, p4), and(p1, p2, p4, p3). - If any of these calls return
true, the points form a square. Otherwise, they do not.
Walkthrough
For each of the three possible pairings of diagonals, we check if the resulting quadrilateral is a square. A quadrilateral is a square if all four of its sides are equal in length and its two diagonals are also equal in length. This check ensures both four equal sides (property of a rhombus) and four right angles (property of a rectangle).
We can define a helper function isSquare(p1, p2, p3, p4) that assumes p1, p2, p3, p4 is the cyclic order of vertices. This function calculates the lengths of the four sides (p1-p2, p2-p3, p3-p4, p4-p1) and the two diagonals (p1-p3, p2-p4). If the four sides are equal (and non-zero) and the two diagonals are equal, it's a square.
The main function then calls this isSquare function for the three possible cyclic orderings:
(p1, p2, p3, p4)(p1, p3, p2, p4)(p1, p2, p4, p3)If any of these configurations form a square, we returntrue. To avoid floating-point issues, we work with squared distances.
class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { // Check the 3 possible configurations of a square. // The arguments to isSquare are the vertices in cyclic order. return isSquare(p1, p2, p3, p4) || isSquare(p1, p3, p2, p4) || isSquare(p1, p2, p4, p3); } // Checks if p1-p2-p3-p4 form a square in this cyclic order. private boolean isSquare(int[] p1, int[] p2, int[] p3, int[] p4) { long d12 = distSq(p1, p2); long d23 = distSq(p2, p3); long d34 = distSq(p3, p4); long d41 = distSq(p4, p1); long diag13 = distSq(p1, p3); long diag24 = distSq(p2, p4); // Check for non-zero side length, four equal sides, and two equal diagonals. return d12 > 0 && d12 == d23 && d23 == d34 && d34 == d41 && diag13 == diag24; } private long distSq(int[] p1, int[] p2) { long dx = p1[0] - p2[0]; long dy = p1[1] - p2[1]; return dx * dx + dy * dy; }}Complexity
Time
O(1) - The number of points is fixed at 4. We perform a constant number of distance calculations and comparisons, regardless of the coordinate values.
Space
O(1) - We do not use any auxiliary data structures that scale with input size.
Trade-offs
Pros
It correctly solves the problem by exhaustively checking all valid geometric configurations.
Cons
The logic is more complex than necessary, involving permutations of points which can be tricky to reason about and implement correctly.
It performs more distance calculations than the more optimized approach.
A more elegant and efficient approach relies on the geometric properties of a square concerning the distances between its vertices. For any four points, there are 4C2 = 6 possible distances between pairs of points. If these points form a square, these 6 distances will consist of four equal side lengths and two equal diagonal lengths. Furthermore, the squared diagonal length will be exactly twice the squared side length (a consequence of the Pythagorean theorem).
Algorithm
- Define a helper function
distSq(a, b)to compute the squared distance between two points. - Create an array to store the 6 squared distances between all unique pairs of the four points.
- Calculate and populate the 6 squared distances.
- Sort the distances array in non-decreasing order.
- Check if the sorted distances satisfy the properties of a square:
- The smallest distance (side length) must be greater than 0.
- The first four distances must be equal (four equal sides).
- The last two distances must be equal (two equal diagonals).
- The squared diagonal length must be twice the squared side length.
- If all conditions are met, return
true; otherwise, returnfalse.
Walkthrough
This method avoids dealing with permutations and orderings explicitly. Instead, we compute all 6 squared distances between the four points and analyze the resulting values. The algorithm is as follows:
- Calculate the 6 squared distances between each pair of the four points.
- Store these 6 values in an array.
- Sort the array of distances.
After sorting, if the points form a valid square, the array of squared distances must follow a specific pattern: the first four elements must be equal (the squared side length), and the last two elements must be equal (the squared diagonal length).
We then verify the following conditions on the sorted array
d:
d[0] > 0: This ensures the side length is positive, which implies that no two points are coincident.d[0] == d[1] == d[2] == d[3]: This confirms that there are four equal sides.d[4] == d[5]: This confirms that there are two equal diagonals.d[4] == 2 * d[0]: This verifies the Pythagorean relationship between the side and the diagonal (diagonal^2 = 2 * side^2). If all these conditions are met, the points form a square.
import java.util.Arrays; class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { long[] distances = { distSq(p1, p2), distSq(p1, p3), distSq(p1, p4), distSq(p2, p3), distSq(p2, p4), distSq(p3, p4) }; Arrays.sort(distances); // A square has 4 equal sides and 2 equal diagonals. // Also, diagonal^2 = 2 * side^2. // After sorting, distances[0] to distances[3] should be the sides, // and distances[4] to distances[5] should be the diagonals. return distances[0] > 0 && distances[0] == distances[1] && distances[1] == distances[2] && distances[2] == distances[3] && distances[4] == distances[5] && distances[4] == 2 * distances[0]; } private long distSq(int[] p1, int[] p2) { long dx = p1[0] - p2[0]; long dy = p1[1] - p2[1]; return dx * dx + dy * dy; }}Complexity
Time
O(1) - The number of operations is constant. We compute 6 distances, sort a fixed-size array of 6 elements, and perform a few comparisons.
Space
O(1) - We use an array of fixed size 6 to store the distances.
Trade-offs
Pros
Highly efficient with a minimal number of calculations.
The logic is simple, elegant, and robust, as it does not depend on the order of input points.
Less prone to implementation errors compared to permutation-based approaches.
Cons
The underlying geometric insight might be slightly less obvious than directly checking geometric configurations.
Solutions
Solution
class Solution {public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4); }private boolean check(int[] a, int[] b, int[] c) { int x1 = a[0], y1 = a[1]; int x2 = b[0], y2 = b[1]; int x3 = c[0], y3 = c[1]; int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3); int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3); if (d1 == d2 && d1 + d2 == d3 && d1 > 0) { return true; } if (d1 == d3 && d1 + d3 == d2 && d1 > 0) { return true; } if (d2 == d3 && d2 + d3 == d1 && d2 > 0) { return true; } return false; }}class Solution {public: bool validSquare(vector<int> &p1, vector<int> &p2, vector<int> &p3, vector<int> &p4) { return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4); } bool check(vector<int> &a, vector<int> &b, vector<int> &c) { int x1 = a[0], y1 = a[1]; int x2 = b[0], y2 = b[1]; int x3 = c[0], y3 = c[1]; int d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); int d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3); int d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3); if (d1 == d2 && d1 + d2 == d3 && d1 > 0) return true; if (d1 == d3 && d1 + d3 == d2 && d1 > 0) return true; if (d2 == d3 && d2 + d3 == d1 && d2 > 0) return true; return false; }};class Solution: def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool: def check(a, b, c): (x1, y1), (x2, y2), (x3, y3) = a, b, c d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3) d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3) return any([d1 == d2 and d1 + d2 == d3 and d1, d2 == d3 and d2 + d3 == d1 and d2, d1 == d3 and d1 + d3 == d2 and d1, ]) return (check(p1, p2, p3) and check(p2, p3, p4) and check(p1, p3, p4) and check(p1, p2, p4))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.