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 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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The problem of detecting whether four points can form a square boils down to ensuring that there are two unique distances: the side of the square and the diagonal (which is the hypotenuse of the two sides of a right angle triangle formed by two consecutive sides).
For four points to form a square:
- The shortest distances (there should be 4 of them) are the sides of the square.
- The longest distances (there should be 2 of them) are the diagonals.
To solve this brute force, we calculate the distance between each pair of given points and then check the distribution of these distances.
Code:
- Time Complexity: O(1). Simple calculations with a constant amount of data (fixed number of operations for distance calculation).
- Space Complexity: O(1). A constant number of data structures used.
2. Sorting and Comparison
Intuition:
We can simplify the check by sorting the points and then analyzing the ordered sequence of distances. The key observation is:
- If you sort points based on their x-coordinate (and secondarily upon y-coordinate if x's are equal), a square’s points will have inherent order allowing easy direct pairwise comparison.
We can calculate squared distances from a fixed reference, then check fixed positions' conditions of distances.
Code:
- Time Complexity: O(1), primarily due to the fixed nature of point sorting and distance parsing, despite operationally implementing a constant array flow.
- Space Complexity: O(1), since limited data-consuming structures are wielded.