# LeetCode 593: Valid Square

## Problem Restatement

We are given four points in 2D space:

```python
p1, p2, p3, p4
```

Each point is represented as:

```python
[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](https://leetcode.com/problems/valid-square/), [github.com](https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0593.Valid%20Square/README_EN.md))

## Input and Output

| Item | Meaning |
|---|---|
| `p1`, `p2`, `p3`, `p4` | Four 2D points |
| Output | `True` if they form a square, otherwise `False` |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
True
```

These four points form a unit square.

Example 2:

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

Output:

```python
False
```

The side lengths and angles do not form a square.

Example 3:

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

Output:

```python
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:

```python
[[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]`:

```python
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:

```text
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | There are always six pairwise distances |
| Space | `O(1)` | The distance list has fixed size |

## Implementation

```python
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:

```python
points = [p1, p2, p3, p4]
```

The helper computes squared distance:

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

Then we compute all six pairwise distances:

```python
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:

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

The diagonals should occupy the last two positions:

```python
distances[4] == distances[5]
```

This check excludes duplicate points:

```python
distances[0] > 0
```

This check ensures the diagonal is longer than the side:

```python
distances[3] < distances[4]
```

## Set-Based Implementation

The same idea can be written more compactly.

```python
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

```python
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:

| Test | Why |
|---|---|
| Unit square | Basic valid square |
| Bad fourth point | Not a square |
| Rotated square | Orientation-independent check |
| Duplicate point | Side length must be positive |
| Rectangle | Equal diagonals but unequal sides |
| Diamond shape | Rotated valid square |