Valid Square

Problem Description

Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square. 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).

Key Insights

• A square has four equal-length sides.
• The diagonals of a square are equal and longer than the sides.
• To determine if the points form a square, we can calculate the distances between each pair of points.
• There should be exactly two unique distances: one for the sides and one for the diagonals.

Space and Time Complexity

Time Complexity: O(1) - The number of computations does not depend on the input size as we always have a fixed number of points (4). Space Complexity: O(1) - We are using a fixed amount of space for storing distances.

Solution

To determine if four points form a valid square, we can follow these steps:

1. Calculate the squared distances between all pairs of points. This avoids the need for floating-point arithmetic.
2. Store these distances in a set to identify unique distances.
3. For a valid square, there should be exactly two unique distances in the set: one for the sides (which should occur 4 times) and one for the diagonals (which should occur 2 times).

Code Solutions