Valid Square

Medium

Google

2 views

Topics:

Arrays

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 pᵢ is represented as [xᵢ, yᵢ]. 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).

For example:

p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] should return true
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] should return false
p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1] should return true

Write a function to solve this problem. Consider edge cases such as:

What should the function return if two or more points are the same?
What should the function return if all four points are on the same line?

How would you optimize your solution for better performance?

Valid Square

Medium

Google

2 views

Topics:

Arrays

For example:

p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] should return true
p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] should return false
p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1] should return true

Write a function to solve this problem. Consider edge cases such as:

What should the function return if two or more points are the same?
What should the function return if all four points are on the same line?

How would you optimize your solution for better performance?

Solution

Naive Solution: Brute Force

A brute-force approach involves calculating all pairwise distances between the four points and checking if the conditions for a square are met.

Calculate the distances between all six pairs of points.
Check if there are four equal sides and two equal diagonals.
Ensure that the side length is greater than zero to avoid degenerate cases.

Code (Python)

def dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def valid_square_brute_force(p1, p2, p3, p4):
    distances = sorted([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)])
    
    # Check if four sides are equal and non-zero, and two diagonals are equal
    if distances[0] > 0 and distances[0] == distances[1] == distances[2] == distances[3] and distances[4] == distances[5]:
        return True
    else:
        return False

Time Complexity: O(1)

Since we always have a fixed number of calculations (distances between 6 pairs), the time complexity is constant.

Space Complexity: O(1)

We use a fixed amount of extra space to store the distances.

Optimal Solution: Using a Set

An optimized approach also involves calculating distances, but leverages a set to efficiently determine if we have the required side and diagonal lengths.

Calculate all six pairwise distances.
Insert all distances into a set.
If the set size is 2, it implies we have two distinct lengths (side and diagonal).
Check if the diagonal length is twice the side length (using the Pythagorean theorem for a square, diagonal = side * sqrt(2), so diagonal^2 = 2 * side^2).

Edge Cases:

Duplicate Points: If any two points are the same, the distance between them is zero, which can lead to incorrect results if not handled.
Points forming a line or other shapes: The algorithm should specifically check for the square condition and return false for other shapes.
Zero Length: The side length must be greater than zero.

Code (Python)

def dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def valid_square(p1, p2, p3, p4):
    distances = [dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)]
    unique_distances = set(distances)

    if 0 in unique_distances:
        return False
        
    if len(unique_distances) != 2:
        return False

    side_sq, diag_sq = sorted(unique_distances)
    return diag_sq == 2 * side_sq

Time Complexity: O(1)

We still have a fixed number of calculations and set operations, so the time complexity remains constant.

Space Complexity: O(1)

We use a fixed amount of extra space to store the unique distances in the set. The set will contain at most two elements.

Solution

Naive Solution: Brute Force

A brute-force approach involves calculating all pairwise distances between the four points and checking if the conditions for a square are met.

Calculate the distances between all six pairs of points.
Check if there are four equal sides and two equal diagonals.
Ensure that the side length is greater than zero to avoid degenerate cases.

Code (Python)

def dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def valid_square_brute_force(p1, p2, p3, p4):
    distances = sorted([dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)])
    
    # Check if four sides are equal and non-zero, and two diagonals are equal
    if distances[0] > 0 and distances[0] == distances[1] == distances[2] == distances[3] and distances[4] == distances[5]:
        return True
    else:
        return False

Time Complexity: O(1)

Since we always have a fixed number of calculations (distances between 6 pairs), the time complexity is constant.

Space Complexity: O(1)

We use a fixed amount of extra space to store the distances.

Optimal Solution: Using a Set

An optimized approach also involves calculating distances, but leverages a set to efficiently determine if we have the required side and diagonal lengths.

Calculate all six pairwise distances.
Insert all distances into a set.
If the set size is 2, it implies we have two distinct lengths (side and diagonal).
Check if the diagonal length is twice the side length (using the Pythagorean theorem for a square, diagonal = side * sqrt(2), so diagonal^2 = 2 * side^2).

Edge Cases:

Duplicate Points: If any two points are the same, the distance between them is zero, which can lead to incorrect results if not handled.
Points forming a line or other shapes: The algorithm should specifically check for the square condition and return false for other shapes.
Zero Length: The side length must be greater than zero.

Code (Python)

def dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def valid_square(p1, p2, p3, p4):
    distances = [dist(p1, p2), dist(p1, p3), dist(p1, p4), dist(p2, p3), dist(p2, p4), dist(p3, p4)]
    unique_distances = set(distances)

    if 0 in unique_distances:
        return False
        
    if len(unique_distances) != 2:
        return False

    side_sq, diag_sq = sorted(unique_distances)
    return diag_sq == 2 * side_sq

Time Complexity: O(1)

We still have a fixed number of calculations and set operations, so the time complexity remains constant.

Space Complexity: O(1)

We use a fixed amount of extra space to store the unique distances in the set. The set will contain at most two elements.