Watch 10 video solutions for Valid Square, a medium level problem involving Math, Geometry. This walkthrough by Knowledge Center has 5,998 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem 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 | 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 |