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 <= 104This 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).
JavaScript
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.
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.
C++
Time Complexity: O(1) - Fixed operations per four points.
Space Complexity: O(1) - Requires a constant amount of space for storing calculations.
| 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. |
Valid Perfect Square - Leetcode 367 - Python • NeetCode • 39,742 views views
Watch 9 more video solutions →Practice Valid Square with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor