Valid Square — Solution in Python, Java & C++
Valid Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Valid Square is a medium coding problem on math and geometry, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Geometry
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given four points p1, p2, p3 and p4 in the plane, each as [x, y] with integer coordinates. They are listed in no particular order.
Return true if the four points are the corners of a square. The square does not have to be aligned with the axes, but it must have positive side length: four sides of equal positive length and four right angles.
Example 1
Input: p1 = [1,0], p2 = [3,1], p3 = [2,3], p4 = [0,2]
Output: true
Explanation: A square tilted by the vector (2,1): every side has squared length 5 and both diagonals have squared length 10.
Example 2
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output: false
Example 3
Input: p1 = [5,5], p2 = [5,5], p3 = [5,5], p4 = [5,5]
Output: false
Explanation: A single point is not a square.
Constraints
p1.length == p2.length == p3.length == p4.length == 2-10^4 <= xi, yi <= 10^4
Hints for Valid Square
Hint 1
The input order means nothing, so look at all six pairwise distances instead of walking around the shape.
Hint 2
Squared distances stay integers — never take a square root.
Hint 3
In a square the four smallest of those six values are equal and positive, and the two largest are equal and exactly twice as big.
How to solve Valid Square
A square is pinned down by its six pairwise distances: four equal sides and two equal diagonals, each diagonal twice the side when squared. Sorting the six squared distances lets you check that without knowing which point is which corner.
Approach
- Compute the squared distance for each of the six pairs of points.
- Sort the six values.
- Return
trueexactly when the smallest is positive, the first four are equal, the last two are equal, and the last equals twice the first.
Why it works
For a real square the four sides are the four smallest distances and the diagonals (squared length 2s) are the two largest, so the test passes. Conversely, suppose four pairs share the squared length s > 0 and the other two share 2s. The two long pairs cannot share a point — a point at squared distance 2s from two others, with those two at distance s from each other and everything else s, is impossible — so the long pairs are two disjoint 'diagonals' and the short pairs form a closed 4-cycle with equal sides, a rhombus. A rhombus with equal diagonals is a square, and d² = 2s² confirms it.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Duplicate points give zero distances; insist the smallest squared distance is positive.
- Checking only 'four equal, two equal' without the factor of 2 is the usual shortcut — it is safe on integer points, but the explicit check costs nothing and does not lean on that fact.
- Do not assume
p1, p2, p3, p4go around the square in order.
Reference solution
Python
from typing import List
def validSquare(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
pts = [p1, p2, p3, p4]
d = []
for i in range(4):
for j in range(i + 1, 4):
dx = pts[i][0] - pts[j][0]
dy = pts[i][1] - pts[j][1]
d.append(dx * dx + dy * dy)
d.sort()
return d[0] > 0 and d[0] == d[3] and d[4] == d[5] and d[4] == 2 * d[0]Java
public static boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[][] pts = { p1, p2, p3, p4 };
long[] d = new long[6];
int k = 0;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
long dx = pts[i][0] - pts[j][0];
long dy = pts[i][1] - pts[j][1];
d[k++] = dx * dx + dy * dy;
}
}
Arrays.sort(d);
return d[0] > 0 && d[0] == d[3] && d[4] == d[5] && d[4] == 2 * d[0];
}C++
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<vector<int>> pts = { p1, p2, p3, p4 };
vector<long long> d;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
long long dx = pts[i][0] - pts[j][0];
long long dy = pts[i][1] - pts[j][1];
d.push_back(dx * dx + dy * dy);
}
}
sort(d.begin(), d.end());
return d[0] > 0 && d[0] == d[3] && d[4] == d[5] && d[4] == 2 * d[0];
}JavaScript
var validSquare = function(p1, p2, p3, p4) {
var pts = [p1, p2, p3, p4];
var d = [];
for (var i = 0; i < 4; i++) {
for (var j = i + 1; j < 4; j++) {
var dx = pts[i][0] - pts[j][0];
var dy = pts[i][1] - pts[j][1];
d.push(dx * dx + dy * dy);
}
}
d.sort(function(a, b) { return a - b; });
return d[0] > 0 && d[0] === d[3] && d[4] === d[5] && d[4] === 2 * d[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.