Algorithm
Problem Name: 593. Valid Square
Problem Link: https://leetcode.com/problems/valid-square/
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[][] points = {p1, p2, p3, p4};
Arrays.sort(points, (i1, i2) -> i2[0] == i1[0] ? i1[1] - i2[1] : i1[0] - i2[0]);
return (
getDistance(points[0], points[1]) != 0 &&
getDistance(points[0], points[1]) == getDistance(points[1], points[3]) &&
getDistance(points[1], points[3]) == getDistance(points[3], points[2]) &&
getDistance(points[3], points[2]) == getDistance(points[2], points[0]) &&
getDistance(points[0],points[3])==getDistance(points[1],points[2])
);
}
private double getDistance(int[] p1, int[] p2) {
return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
}
}
Input
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output
true
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const validSquare = function(p1, p2, p3, p4) {
const lenArr = [
distance(p1, p2),
distance(p1, p3),
distance(p1, p4),
distance(p2, p3),
distance(p2, p4),
distance(p3, p4)
]
const obj = {}
for (let el of lenArr) {
if (obj[el] != null) obj[el] += 1
else obj[el] = 1
}
const keys = Object.keys(obj)
return keys.length === 2 && (obj[keys[0]] === 2 || obj[keys[1]] === 2)
}
function distance(p1, p2) {
return Math.sqrt(Math.pow(p1[1] - p2[1], 2) + Math.pow(p1[0] - p2[0], 2))
}
Input
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output
true
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def validSquare(self, p1, p2, p3, p4):
"""
:type p1: List[int]
:type p2: List[int]
:type p3: List[int]
:type p4: List[int]
:rtype: bool
"""
from itertools import combinations as cb
def D(C):
return (C[0][0] - C[1][0]) ** 2 + (C[0][1] - C[1][1]) ** 2
S = set(map(D, cb((p1, p2, p3, p4), 2)))
return len(S) == 2 and 0 not in S
Input
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
Output
false