LeetCode Solutions Blog

Valid Square

Number: 593

Difficulty: Medium

Paid? No

Problem Description

Given four points in the 2D plane (provided in any order), determine whether these points form a valid square. A valid square must have four equal sides with positive length and four right angles.

Key Insights

Calculate all six pairwise squared distances between the four points.
For a valid square, there should be exactly two unique distances: the smaller one representing the sides (appearing exactly 4 times) and the larger one representing the diagonals (appearing exactly 2 times).
Duplicate points or a zero distance immediately disqualify the formation of a square.

Space and Time Complexity

Time Complexity: O(1) (since the number of points is fixed) Space Complexity: O(1) (constant extra space used for computations)

Solution

We start by calculating the squared Euclidean distance between every pair of points to avoid the complications of floating point precision. We then count the frequency of these distances. A valid square must show exactly two distinct distances: one (side length squared) should appear 4 times and the other (diagonal length squared) should appear 2 times. This provides a robust check for both equal sides and the correct geometric property (diagonals in a square are longer than sides and appear exactly twice). The solution uses simple iteration over the fixed set of point pairs to tally frequencies and then verifies the required counts.

Code Solutions

# Define a function to calculate squared distance between two points
def squared_distance(p, q):
    # Calculate the squared difference in x and y coordinates
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

def validSquare(p1, p2, p3, p4):
    # List of all points
    points = [p1, p2, p3, p4]
    distances = []
    
    # Compute squared distances for each unique pair among 4 points (6 pairs in total)
    for i in range(4):
        for j in range(i+1, 4):
            dist = squared_distance(points[i], points[j])
            if dist == 0:
                # If two points are the same, it's not a square
                return False
            distances.append(dist)

    # Use a dictionary to count frequency of each unique distance
    freq = {}
    for d in distances:
        freq[d] = freq.get(d, 0) + 1
        
    # There must be exactly 2 distinct distances 
    if len(freq) != 2:
        return False

    # Identify side and diagonal distances based on frequency count
    side, diag = sorted(freq, key=lambda x: (freq[x], x))
    # For a valid square, the side should appear 4 times and diagonal 2 times
    return freq[side] == 4 and freq[diag] == 2

# Example usage:
print(validSquare([0,0], [1,1], [1,0], [0,1]))  # Expected output: True