Valid Square - Solution & Explanation
Problem Statement
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.
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).
Code
Python
JavaScript
Complexity
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.
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.
Complexity
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
Try this approach in the editor →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 | — |
Detailed 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 |
Video Solution
Valid Square | LeetCode 593 | C++, Java, Python • Knowledge Center • 6,040 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Valid Square easy or hard?
Valid Square Python/Java solution
How to solve Valid Square in O(n)?
What is the best approach for Valid Square?
Is Valid Square asked at Google/Amazon/Meta?
What data structure is used in Valid Square?
What is the time complexity of Valid Square?
Ready to solve this problem?
Practice Valid Square with our built-in code editor and test cases.
Practice on FleetCode