Valid Square solution and explanation
Google
9 more videos on this problem
Valid Square | LeetCode 593 | C++, Java, PythonKnowledge Center · 11:25 · 6K views
Valid Square | valid square | leetcode 593 | distanceNaresh Gupta · 7:43 · 2K views
Valid Square | Live Coding with Explanation | Leetcode #593Algorithms Made Easy · 4:26 · 2K views
Valid Square | Leet code 593 | Theory explained + Python codeSai Anish Malla · 18:56 · 1K views
LeetCode 593. Valid SquareHappy Coding · 15:34 · 1K views
தமிழ் |VALID SQUARE | LEETCODE 593 | November challenge | interview problem| java| leetcode problemsAlgo Tamizha · 12:03 · 837 views
Valid Square Leetcode | Leetcode 593 | Leetcode November ChallengeCode Bashers · 9:22 · 646 views
Valid Square | Leetcode Medium | Math | GeometryBinaryMagic · 8:05 · 594 views
LeetCode Live: 593 Valid Square, 04/05/2019Huifeng Guan · 14:25 · 486 views
Daily Leetcode #225: Nov 11, 2020 - 593. Valid SquareProgramming Live with Larry · 6:50 · 342 views
The problem
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 <= 104
Approach overview
Problem Overview: You get four points in a 2D plane. The task is to determine whether these points form a valid square. A valid square has four equal sides and two equal diagonals, with diagonals longer than the sides.
Approach 1: Sort Distances Method (O(1) time, O(1) space)
This approach uses the geometric property that a square has exactly four equal side lengths and two equal diagonal lengths. Compute the squared distance between every pair of points. With four points, there are six pairwise distances. Store these values in an array and sort them. If the first four distances are equal (the sides), the last two are equal (the diagonals), and the side length is not zero, the points form a valid square.
The key insight is that squared distances avoid floating point errors and remove the need for square root operations. Sorting the six distances makes it easy to group the sides and diagonals. Since the number of points is fixed, the complexity remains constant: O(1) time and O(1) space. This approach relies on simple arithmetic from math and geometric distance calculations from geometry.
Approach 2: Vector Multiplication Method (O(1) time, O(1) space)
This method verifies square properties using vectors and dot products. First treat one point as a reference and build vectors to the other points. In a square, adjacent sides must have equal lengths and be perpendicular. You can check perpendicularity by computing the dot product of two vectors; perpendicular vectors produce a dot product of zero. Additionally verify that both side vectors have equal squared lengths.
After identifying two perpendicular edges from the same vertex, confirm that the remaining point matches the expected fourth corner of the square using vector addition. This approach directly encodes square geometry rather than relying on sorted distances. The operations involve vector subtraction, squared magnitude checks, and dot product calculations, all constant-time operations. It is a more explicit application of geometry and vector math.
Recommended for interviews: The sorted distance approach is usually the fastest to implement and the easiest to reason about under pressure. It demonstrates that you understand the defining geometric properties of a square and how to translate them into code. The vector method shows deeper geometric reasoning and familiarity with vector operations, which can stand out in geometry-heavy interviews.
Approach 1: Approach 1: Sort Distances Method
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.
def validSquare(p1, p2, p3, p4):
def dist(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
points = [p1, p2, p3, p4]
dists = sorted(dist(points[i], points[j]) for i in range(4) for j in range(i + 1, 4))
return 0 < dists[0] == dists[1] == dists[2] == dists[3] and dists[4] == dists[5]var validSquare = function(p1, p2, p3, p4) {
function dist(a, b) {
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
}
let points = [p1, p2, p3, p4];
let dists = [];
for (let i = 0; i < 4; i++) {
for (let j = i + 1; j < 4; j++) {
dists.push(dist(points[i], points[j]));
}
}
dists.sort((a, b) => a - b);
return dists[0] > 0 && dists[0] === dists[1] && dists[1] === dists[2] && dists[2] === dists[3] && 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).
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.
Approach 2: Approach 2: Vector Multiplication Method
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.
class Solution {
private int dist(int[] p1, int[] p2) {
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[][] points = {p1, p2, p3, p4};
int[] dists = new int[6];
int idx = 0;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
dists[idx++] = dist(points[i], points[j]);
}
}
Arrays.sort(dists);
return dists[0] > 0 && dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3] && dists[4] == dists[5];
}
}#include <vector>
#include <algorithm>
using namespace std;
class 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];
}
};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.
Time Complexity: O(1) - Fixed operations per four points.
Space Complexity: O(1) - Requires a constant amount of space for storing calculations.
Approach 3: Default Approach
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
check := func(a, b, c []int) bool {
x1, y1 := a[0], a[1]
x2, y2 := b[0], b[1]
x3, y3 := c[0], c[1]
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)
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
}
return check(p1, p2, p3) && check(p1, p3, p4) && check(p1, p2, p4) && check(p2, p3, p4)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort Distances Method | Time Complexity: O(1) - The process involves constant time operations for the four points. |
| Approach 2: Vector Multiplication Method | Time Complexity: O(1) - Fixed operations per four points. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Distances Method | O(1) | O(1) | General solution; simplest way to verify square properties using pairwise distances |
| Vector Multiplication Method | O(1) | O(1) | When you want explicit geometric validation using perpendicular vectors and equal side lengths |
Frequently asked questions
Is Valid Square easy or hard?
Valid Square is rated Medium difficulty. The challenge is recognizing the geometric properties that uniquely define a square and converting them into precise checks using distances or vectors without missing corner cases like duplicate points.
Valid Square Python/Java solution
Python and JavaScript solutions typically use the sorted distance method because it is concise. Java and C++ implementations often demonstrate the vector multiplication approach using dot products and squared magnitudes to confirm perpendicular sides and equal lengths.
How to solve Valid Square in O(n)?
The problem does not scale with input size because exactly four points are provided. All valid solutions run in constant time O(1). Typical implementations compute pairwise squared distances or verify perpendicular vectors using dot products.
What is the best approach for Valid Square?
The sorted distances approach is the most practical solution. Compute the six pairwise squared distances between the four points, sort them, and check that four smallest values are equal sides while the two largest are equal diagonals. The algorithm runs in O(1) time and O(1) space because the number of points is fixed.
Is Valid Square asked at Google/Amazon/Meta?
Geometry validation problems like Valid Square commonly appear in interviews at large tech companies including Amazon, Google, and Meta. They test understanding of distance formulas, vector math, and careful handling of edge cases such as overlapping points.
What data structure is used in Valid Square?
Most solutions only require a small array or list to store pairwise distances between points. The logic mainly relies on geometry calculations such as squared distance and vector dot products rather than complex data structures.
What is the time complexity of Valid Square?
The time complexity is O(1). Only six pairwise distance calculations are required for four points, followed by sorting a constant-size array. Space complexity is also O(1) since only a few variables or a small list of distances are stored.