LeetCode 593: Valid Square

Problem Restatement

We are given four points in 2D space:

p1, p2, p3, p4

Each point is represented as:

[x, y]

We need to return True if these four points form a valid square.

The points are not given in any particular order. A valid square has four equal sides with positive length and four right angles. The coordinates satisfy -10^4 <= x_i, y_i <= 10^4. (leetcode.com, github.com)

Input and Output

Example function shape:

def validSquare(
    p1: list[int],
    p2: list[int],
    p3: list[int],
    p4: list[int],
) -> bool:
    ...

Examples

Example 1:

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

Output:

True

These four points form a unit square.

Example 2:

p1 = [0, 0]
p2 = [1, 1]
p3 = [1, 0]
p4 = [0, 12]

Output:

False

The side lengths and angles do not form a square.

Example 3:

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

Output:

True

This is a square rotated by 45 degrees.

First Thought: Sort Points and Check Edges

One approach is to sort the points and try to identify neighboring points.

But this is easy to get wrong because squares can be rotated.

For example:

[[1, 0], [-1, 0], [0, 1], [0, -1]]

forms a square, but its sides are diagonal relative to the coordinate axes.

So we need a method that does not depend on orientation.

Key Insight

A square has a simple distance pattern among its four points.

There are six pairwise distances among four points.

For a valid square:

1. Four distances are equal side lengths.
2. Two distances are equal diagonal lengths.
3. The side length is positive.
4. The diagonal length is larger than the side length.

So we can compute all six squared distances.

We use squared distance to avoid square roots and floating point precision.

For two points a = [x1, y1] and b = [x2, y2]:

distance_squared = (x1 - x2) ** 2 + (y1 - y2) ** 2

A valid square should produce exactly two distinct nonzero distances.

The smaller distance appears four times.

The larger distance appears two times.

Algorithm

1. Put the four points into a list.
2. Compute the squared distance for every pair of points.
3. Store the six distances.
4. Sort the distances.
5. Check that:
   • the smallest distance is positive,
   • the first four distances are equal,
   • the last two distances are equal,
   • the side distance is smaller than the diagonal distance.

Correctness

There are exactly six distances between four points.

If the four points form a square, then the four edges have the same positive length. These produce four equal smaller squared distances. The two diagonals also have the same length, and each diagonal is longer than a side. Therefore, the sorted distance list has the form:

side, side, side, side, diagonal, diagonal

with side > 0 and diagonal > side.

Conversely, suppose the six squared distances have exactly that pattern. Then each point is connected to two other points at the smaller distance and one opposite point at the larger distance. This is exactly the distance structure of four vertices of a square. The positive side length excludes duplicate points. The two equal larger distances are the diagonals. Therefore, the four points form a valid square.

Thus, the algorithm returns True exactly when the points form a square.

Complexity

The input always has exactly four points.

Implementation

class Solution:
    def validSquare(
        self,
        p1: list[int],
        p2: list[int],
        p3: list[int],
        p4: list[int],
    ) -> bool:
        points = [p1, p2, p3, p4]

        def dist(a: list[int], b: list[int]) -> int:
            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

        distances = []

        for i in range(4):
            for j in range(i + 1, 4):
                distances.append(dist(points[i], points[j]))

        distances.sort()

        return (
            distances[0] > 0
            and distances[0] == distances[1] == distances[2] == distances[3]
            and distances[4] == distances[5]
            and distances[3] < distances[4]
        )

Code Explanation

We collect the points:

points = [p1, p2, p3, p4]

The helper computes squared distance:

def dist(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

Then we compute all six pairwise distances:

for i in range(4):
    for j in range(i + 1, 4):
        distances.append(dist(points[i], points[j]))

After sorting, the side lengths should occupy the first four positions:

distances[0] == distances[1] == distances[2] == distances[3]

The diagonals should occupy the last two positions:

distances[4] == distances[5]

This check excludes duplicate points:

distances[0] > 0

This check ensures the diagonal is longer than the side:

distances[3] < distances[4]

Set-Based Implementation

The same idea can be written more compactly.

class Solution:
    def validSquare(
        self,
        p1: list[int],
        p2: list[int],
        p3: list[int],
        p4: list[int],
    ) -> bool:
        points = [p1, p2, p3, p4]

        def dist(a: list[int], b: list[int]) -> int:
            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

        distances = [
            dist(points[i], points[j])
            for i in range(4)
            for j in range(i + 1, 4)
        ]

        return 0 not in distances and len(set(distances)) == 2

This works because a square has exactly two nonzero pairwise distances: side length and diagonal length.

Testing

def run_tests():
    s = Solution()

    assert s.validSquare([0, 0], [1, 1], [1, 0], [0, 1]) is True
    assert s.validSquare([0, 0], [1, 1], [1, 0], [0, 12]) is False
    assert s.validSquare([1, 0], [-1, 0], [0, 1], [0, -1]) is True
    assert s.validSquare([0, 0], [0, 0], [1, 1], [1, 0]) is False
    assert s.validSquare([0, 0], [2, 0], [2, 1], [0, 1]) is False
    assert s.validSquare([0, 0], [1, 1], [2, 0], [1, -1]) is True

    print("all tests passed")

run_tests()

Test meaning: