LeetCode 593: Valid Square Solution in Python – A Step-by-Step Guide

Imagine you’re handed four points on a map—like [(0,0), (1,1), (1,0), (0,1)]—and your task is to figure out if they form a perfect square, such as confirming these points do, with equal sides and right angles. That’s the geometric challenge of LeetCode 593: Valid Square, a medium-level problem that’s a fantastic way to practice coordinate geometry in Python. We’ll explore two solutions: the Best Solution, a distance-based validation with set checking that’s efficient and clever, and an Alternative Solution, a brute-force coordinate check that’s thorough but less optimized. With detailed examples, clear code, and a friendly tone—especially for the distance approach—this guide will help you square those points, whether you’re new to coding or leveling up. Let’s measure those sides and start validating!

What Is LeetCode 593: Valid Square?

In LeetCode 593: Valid Square, you’re given four points as a list of tuples p1, p2, p3, p4, where each tuple (x, y) represents coordinates on a 2D plane, and your task is to return True if these points form a valid square and False otherwise. A valid square requires four equal sides and four right angles (or equivalently, equal diagonals). For example, with p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1], the result is True because they form a square with side length 1 and right angles. This problem builds on LeetCode 287: Find the Duplicate Number for pattern recognition but focuses on geometric properties using distances.

Problem Statement

Input: p1, p2, p3, p4 (List[int])—four points as (x, y) coordinates.
Output: Boolean—True if points form a square, False otherwise.
Rules: Four equal sides, four right angles; points may not be in order; no three points collinear.

Constraints

p1.length == p2.length == p3.length == p4.length == 2
-10⁴ <= x, y <= 10⁴
Points are distinct

Examples

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

Output: True
Forms a square with side length 1, diagonals √2.

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,2]

Output: False
Unequal sides (e.g., 0-2 ≠ 1).

Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]

Output: True
Square centered at origin, side length √2.

Understanding the Problem: Checking a Square

To solve LeetCode 593: Valid Square in Python, we need to determine if four points form a square by verifying equal side lengths and right angles (or equal diagonals), handling coordinates within [-10⁴, 10⁴] efficiently. A brute-force approach checking all possible side-angle combinations could work but is tedious (O(1) but complex). Instead, a distance-based method computes all pairwise distances in O(1) time (since n=4 is fixed), using a set to check for exactly two unique distances (sides and diagonals) in the correct frequency, leveraging geometric properties. We’ll explore:

Best Solution (Distance-Based Validation with Set Checking): O(1) time, O(1) space—fast and optimal.
Alternative Solution (Brute-Force Coordinate Checking): O(1) time, O(1) space—thorough but cumbersome.

Let’s dive into the distance solution with a friendly breakdown!

Best Solution: Distance-Based Validation with Set Checking

Why Distance Wins

The distance-based validation with set checking is the best for LeetCode 593 because it determines if four points form a square in O(1) time and O(1) space (since n=4 is constant) by calculating all pairwise distances, using a set to verify exactly two unique values (side length and diagonal), and ensuring their frequencies match a square’s properties (4 sides, 2 diagonals). It’s like measuring a plot of land, checking if the distances fit a perfect square—all in a quick, clever measurement!

How It Works

Think of this as a geometry surveyor:

Step 1: Compute All Distances:

Calculate Euclidean distances between all 6 pairs of points.

Step 2: Use Set for Uniqueness:

Add distances to a set; expect exactly 2 values (side, diagonal).

Step 3: Validate Frequencies:

Count occurrences: 4 sides (smaller distance), 2 diagonals (larger distance).
Zero not allowed (no overlapping points).

Step 4: Return Result:

True if conditions met, False otherwise.

Why It Works:

Square has 4 equal sides, 2 equal diagonals.
Set simplifies checking unique distances.

It’s like a square-measuring maestro!

Step-by-Step Example

Example: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

Step 1: Compute distances:

(0,0)-(1,1): √((1-0)² + (1-0)²) = √2.
(0,0)-(1,0): √1 = 1.
(0,0)-(0,1): √1 = 1.
(1,1)-(1,0): √1 = 1.
(1,1)-(0,1): √1 = 1.
(1,0)-(0,1): √2.

Step 2: Set = {1, √2}.
Step 3: Frequencies:

1: 4 (sides), √2: 2 (diagonals).
No 0, exactly 2 values, matches square pattern.

Step 4: Return True.
Result: True.

Example: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,2]

Step 1: Distances:

(0,0)-(1,1): √2.
(0,0)-(1,0): 1.
(0,0)-(0,2): 2.
(1,1)-(1,0): 1.
(1,1)-(0,2): √2.
(1,0)-(0,2): √5.

Step 2: Set = {1, √2, 2, √5}.
Step 3: 4 unique distances, not a square.
Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        # Step 1: Helper to compute squared distance (avoid floating-point precision)
        def dist(p, q):
            return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

        # Step 2: List all points
        points = [p1, p2, p3, p4]

        # Step 3: Compute all pairwise distances
        distances = []
        for i in range(4):
            for j in range(i + 1, 4):
                d = dist(points[i], points[j])
                distances.append(d)

        # Step 4: Sort distances and check conditions
        distances.sort()

        # Must have exactly 6 distances (4 sides, 2 diagonals)
        # No zero (distinct points), 4 equal sides, 2 equal diagonals
        return (len(distances) == 6 and 
                distances[0] > 0 and 
                distances[0] == distances[1] == distances[2] == distances[3] and 
                distances[4] == distances[5])

Lines 3-5: Distance helper: Squared distance avoids √ precision issues.
Line 8: Group points into list for iteration.
Lines 11-15: Compute 6 pairwise distances.
Lines 18-22: Validate:

6 distances present.
No zero (distinct points).
First 4 equal (sides), last 2 equal (diagonals).

Time Complexity: O(1)—fixed 4 points, 6 distances.
Space Complexity: O(1)—fixed-size list.

It’s like a square-validating genius!

Alternative Solution: Brute-Force Coordinate Checking

Why an Alternative Approach?

The brute-force coordinate checking approach tests all permutations of the four points to find a square configuration, verifying side lengths and angles, running in O(1) time (since n=4 is fixed) and O(1) space. It’s thorough but cumbersome, making it a baseline for understanding or when distance sets seem abstract.

How It Works

Picture this as a square-hunting brute:

Step 1: Generate all point orderings (permutations).
Step 2: For each ordering, check if consecutive sides are equal and perpendicular.
Step 3: Return True if any valid square found.
Step 4: Return False if none found.

It’s like a trial-and-error square finder!

Step-by-Step Example

Example: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

Step 1: Permutation [(0,0), (1,0), (1,1), (0,1)]:

Sides: 1, 1, 1, 1.
Dot products (90°): (1,0)·(0,1) = 0, etc., all 0.

Step 2: Valid square found.
Result: True.

Code for Brute-Force Approach

from itertools import permutations

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        def dist(p, q):
            return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

        def dot(p, q):
            return (p[0] * q[0]) + (p[1] * q[1])

        points = [p1, p2, p3, p4]
        for perm in permutations(points):
            p0, p1, p2, p3 = perm
            sides = [
                dist(p0, p1),
                dist(p1, p2),
                dist(p2, p3),
                dist(p3, p0)
            ]
            vectors = [
                (p1[0] - p0[0], p1[1] - p0[1]),
                (p2[0] - p1[0], p2[1] - p1[1]),
                (p3[0] - p2[0], p3[1] - p2[1]),
                (p0[0] - p3[0], p0[1] - p3[1])
            ]
            angles = [
                dot(vectors[0], vectors[1]),
                dot(vectors[1], vectors[2]),
                dot(vectors[2], vectors[3]),
                dot(vectors[3], vectors[0])
            ]
            if (all(side == sides[0] and side > 0 for side in sides) and 
                all(angle == 0 for angle in angles)):
                return True
        return False

Lines 5-12: Helpers for distance and dot product.
Lines 15-34: Check each permutation for equal sides and right angles.
Time Complexity: O(1)—fixed 24 permutations.
Space Complexity: O(1)—fixed-size lists.

It’s a brute-force square tester!

Comparing the Two Solutions

Distance (Best):

Pros: O(1), O(1), elegant and fast.
Cons: Abstract distance logic.

Brute-Force (Alternative):

Pros: O(1), O(1), explicit geometry.
Cons: Cumbersome permutations.

Distance wins for simplicity!

Additional Examples and Edge Cases

Collinear: False.
Overlapping points: False.
Non-square rectangle: False.

Distance handles them all!

Complexity Recap

Distance: Time O(1), Space O(1).
Brute-Force: Time O(1), Space O(1).

Distance’s the clarity champ!

Key Takeaways

Distance: Geometry finesse—learn at Python Basics!
Brute-Force: Exhaustive check.
Squares: Shapes are fun.
Python: Distance or brute, your pick!

Final Thoughts: Validate That Square!

LeetCode 593: Valid Square in Python is a geometric puzzle. Distance-based validation with set checking is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 287: Find the Duplicate Number or LeetCode 223: Rectangle Area. Ready to measure? Head to Solve LeetCode 593 on LeetCode and check that square today!