algoadvance

You are given the coordinates of four points in a 2D space, and you need to determine if these four points can form a square. The coordinates of the points are given as:

Your task is to write a function validSquare(p1, p2, p3, p4) which returns True if the points form a square, otherwise returns False.

Clarifying Questions

  1. Can the points be given in any order?
    • Yes, the points can be given in any order.
  2. Are there any constraints on the values of the coordinates?
    • The coordinate values can be any integers.

Strategy

To determine if the four points form a square, we need to check the following properties:

  1. All four sides of the square should be of equal length.
  2. All diagonals should be of equal length and longer than the sides.

We can compute the squared distance between each pair of points to avoid dealing with floating-point precision issues.

Steps:

  1. Compute the squared distances between each pair of points.
  2. Verify that there are exactly two distinct squared distances: one for the sides and one for the diagonals.
  3. Confirm there are exactly four occurrences of the side length and two occurrences of the diagonal length.

Code

from itertools import combinations

def distance_sq(point1, point2):
    return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2

def validSquare(p1, p2, p3, p4):
    points = [p1, p2, p3, p4]
    
    # Calculate squared distances between each pair
    dists = [distance_sq(pt1, pt2) for pt1, pt2 in combinations(points, 2)]
    
    # Use a set to get the unique distances
    unique_dists = set(dists)
    
    # To form a valid square, there should be only 2 unique distances
    if len(unique_dists) != 2:
        return False
    
    # Find the count of each unique distance
    dist_count = {dist: dists.count(dist) for dist in unique_dists}
    
    # Valid square should have 4 sides of equal length and 2 equal diagonals
    side_length = min(dist_count.keys())
    diagonal_length = max(dist_count.keys())
    
    return dist_count[side_length] == 4 and dist_count[diagonal_length] == 2

# Example Usage
p1 = [0, 0]
p2 = [1, 1]
p3 = [1, 0]
p4 = [0, 1]

print(validSquare(p1, p2, p3, p4))  # Output should be True

Time Complexity

The time complexity of this solution is O(1) since the number of points is fixed (always 4 points). The space complexity is also O(1) for the same reason. We are just performing a constant amount of work (calculating distances and checking conditions).

Try our interview co-pilot at AlgoAdvance.com