Problem
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-10^4 <= xi, yi <= 10^4
Solution (Java)
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[] distancesSquared = new int[6];
distancesSquared[0] = getDistanceSquared(p1, p2);
distancesSquared[1] = getDistanceSquared(p1, p3);
distancesSquared[2] = getDistanceSquared(p1, p4);
distancesSquared[3] = getDistanceSquared(p2, p3);
distancesSquared[4] = getDistanceSquared(p2, p4);
distancesSquared[5] = getDistanceSquared(p3, p4);
Arrays.sort(distancesSquared);
if (distancesSquared[0] == 0) {
return false;
}
if (distancesSquared[0] != distancesSquared[3]) {
return false;
}
if (distancesSquared[4] != distancesSquared[5]) {
return false;
}
return distancesSquared[5] == 2 * distancesSquared[0];
}
private int getDistanceSquared(int[] p1, int[] p2) {
int deltaX = p2[0] - p1[0];
int deltaY = p2[1] - p1[1];
return deltaX * deltaX + deltaY * deltaY;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).