LeetCode 593 - Valid Square

LeetCode Problem 593

Difficulty: 🟡 Medium
Topics: Math, Geometry

Solution

Problem Understanding

The problem gives four points in a 2D coordinate system and asks whether those four points form a valid square. The points are not provided in any guaranteed order, which means we cannot assume adjacent points or diagonally opposite points are already grouped correctly.

A square must satisfy two geometric properties simultaneously. First, all four sides must have the same positive length. Second, all four interior angles must be exactly 90 degrees. Because the points can appear in arbitrary order, the challenge is determining whether some arrangement of the four points satisfies these conditions.

Each point is represented as a pair of integers [x, y]. The coordinates may be negative, positive, or zero. The function should return true if the four points can form a square, otherwise return false.

The constraints are very small, only four points are involved, so performance is not really limited by input size. However, the problem still requires careful geometric reasoning to avoid incorrect classifications. Floating point arithmetic can introduce precision problems when checking distances or angles, so an integer-based approach is preferable.

Several edge cases are important:

• Multiple points may overlap, producing zero-length sides.
• The points may form a rectangle but not a square.
• The points may form a rhombus with equal sides but non-right angles.
• The points may be collinear.
• The points may already be given in a random order.

A correct solution must handle all of these situations reliably.

Approaches

Brute Force Approach

A brute-force solution tries every possible ordering of the four points and checks whether that ordering forms a square.

For any chosen ordering:

• The four consecutive sides must have equal non-zero length.
• The two diagonals must have equal length.
• Adjacent sides must be perpendicular.

Since there are only four points, there are 4! = 24 possible permutations. For each permutation, we can compute distances and verify the square conditions.

This approach is correct because every possible arrangement is examined. If any ordering forms a square, the algorithm will eventually find it.

However, this approach is unnecessarily complicated. Even though 24 permutations is still constant time, the implementation becomes verbose and error-prone. We can derive a cleaner geometric observation that avoids permutation checking entirely.

Optimal Approach

The key geometric insight is that a square has exactly:

• Four equal side lengths
• Two equal diagonal lengths
• The diagonal length is larger than the side length

If we compute all pairwise distances between four points, there are exactly six distances total:

• Four side distances
• Two diagonal distances

For a valid square:

• The four smallest distances must be equal and greater than zero
• The two largest distances must be equal

This observation completely removes the need to determine point ordering.

We use squared distances instead of actual Euclidean distances. Since square roots preserve ordering, comparing squared distances is sufficient and avoids floating point operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Tries all 24 permutations and validates square properties
Optimal	O(1)	O(1)	Uses pairwise distance frequency properties

Algorithm Walkthrough

1. Store all four points in a list so they can be processed uniformly.
2. Compute the squared distance between every pair of points. Since there are four points, there are exactly six unique pairs.
3. For each pair (a, b), compute:

$d=(x_1-x_2)^2+(y_1-y_2)^2$

Using squared distance avoids floating point precision issues and is sufficient for equality comparisons. 4. Insert all six squared distances into a list. 5. Sort the distance list. After sorting:

• The first four values should represent the four sides.
• The last two values should represent the diagonals.

6. Verify that the smallest distance is greater than zero. This ensures no two points overlap.
7. Check that the first four distances are equal. This confirms all sides have the same length.
8. Check that the final two distances are equal. This confirms both diagonals have the same length.
9. If all conditions pass, return true. Otherwise, return false.

Why it works

A square uniquely produces four equal side lengths and two equal diagonals among its six pairwise distances. No other quadrilateral satisfies this exact pattern while also having non-zero side lengths. Sorting the six distances allows us to separate sides from diagonals without needing to determine the point ordering explicitly.

Python Solution

from typing import List

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

        def squared_distance(a: List[int], b: List[int]) -> int:
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            return dx * dx + dy * dy

        points = [p1, p2, p3, p4]
        distances = []

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

        distances.sort()

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

The implementation begins by defining a helper function to compute squared Euclidean distance between two points. This keeps the main logic clean and avoids repeated code.

All four points are stored in a single list so we can iterate through them systematically. A nested loop generates all six unique point pairs.

Each squared distance is appended to the distances list. After all distances are collected, the list is sorted so the four side lengths naturally appear before the two diagonal lengths.

The final return statement performs all validation checks directly:

• distances[0] > 0 prevents overlapping points
• The first four equal values confirm equal side lengths
• The last two equal values confirm equal diagonals

If every condition holds, the points form a valid square.

Go Solution

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {

	squaredDistance := func(a []int, b []int) int {
		dx := a[0] - b[0]
		dy := a[1] - b[1]
		return dx*dx + dy*dy
	}

	points := [][]int{p1, p2, p3, p4}
	distances := make([]int, 0, 6)

	for i := 0; i < 4; i++ {
		for j := i + 1; j < 4; j++ {
			distances = append(
				distances,
				squaredDistance(points[i], points[j]),
			)
		}
	}

	sort.Ints(distances)

	return distances[0] > 0 &&
		distances[0] == distances[1] &&
		distances[1] == distances[2] &&
		distances[2] == distances[3] &&
		distances[4] == distances[5]
}

The Go implementation closely mirrors the Python solution. A closure is used for the squared distance helper function.

Slices are used to store both the points and computed distances. Since exactly six distances are generated, the distance slice is initialized with capacity 6 to avoid unnecessary reallocations.

Go integer arithmetic is safe here because coordinate values are limited to 10^4, so squared distances remain well within the range of a 32-bit signed integer.

The solution also requires importing the sort package:

import "sort"

Worked Examples

Example 1

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

The algorithm computes all pairwise squared distances.

Pair	Squared Distance
p1-p2	2
p1-p3	1
p1-p4	1
p2-p3	1
p2-p4	1
p3-p4	2

Sorted distances:

Index	Value
0	1
1	1
2	1
3	1
4	2
5	2

The first four distances are equal and non-zero. The final two distances are equal.

Result: true

Example 2

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

Pairwise squared distances:

Pair	Squared Distance
p1-p2	2
p1-p3	1
p1-p4	144
p2-p3	1
p2-p4	122
p3-p4	145

Sorted distances:

Index	Value
0	1
1	1
2	2
3	122
4	144
5	145

The first four distances are not equal.

Result: false

Example 3

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

Pairwise squared distances:

Pair	Squared Distance
p1-p2	4
p1-p3	2
p1-p4	2
p2-p3	2
p2-p4	2
p3-p4	4

Sorted distances:

Index	Value
0	2
1	2
2	2
3	2
4	4
5	4

The pattern matches a square exactly.

Result: true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Exactly six distances are computed and sorted
Space	O(1)	Only a fixed-size list of six distances is stored

Although sorting usually costs O(n log n), the number of distances is always fixed at six. Therefore the runtime is constant. The algorithm does not allocate memory proportional to input size, since the input size itself is constant.

Test Cases

from typing import List

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

        def squared_distance(a: List[int], b: List[int]) -> int:
            dx = a[0] - b[0]
            dy = a[1] - b[1]
            return dx * dx + dy * dy

        points = [p1, p2, p3, p4]
        distances = []

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

        distances.sort()

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

solution = Solution()

assert solution.validSquare(
    [0, 0], [1, 1], [1, 0], [0, 1]
) is True  # standard axis-aligned square

assert solution.validSquare(
    [0, 0], [1, 1], [1, 0], [0, 12]
) is False  # irregular quadrilateral

assert solution.validSquare(
    [1, 0], [-1, 0], [0, 1], [0, -1]
) is True  # rotated square

assert solution.validSquare(
    [0, 0], [2, 0], [2, 1], [0, 1]
) is False  # rectangle but not square

assert solution.validSquare(
    [0, 0], [1, 1], [2, 2], [3, 3]
) is False  # collinear points

assert solution.validSquare(
    [0, 0], [0, 0], [1, 1], [1, 0]
) is False  # duplicate points

assert solution.validSquare(
    [-1, -1], [-1, 1], [1, 1], [1, -1]
) is True  # square with negative coordinates

assert solution.validSquare(
    [10000, 10000],
    [10001, 10000],
    [10001, 10001],
    [10000, 10001]
) is True  # large coordinates

assert solution.validSquare(
    [0, 0], [2, 1], [3, 3], [1, 2]
) is False  # rhombus-like shape without right angles

Test	Why
Standard unit square	Verifies basic valid square detection
Irregular quadrilateral	Ensures unequal sides fail
Rotated square	Confirms orientation independence
Rectangle	Ensures equal diagonals alone are insufficient
Collinear points	Prevents degenerate geometry
Duplicate points	Verifies zero-length sides are rejected
Negative coordinates	Confirms coordinate sign does not matter
Large coordinates	Verifies arithmetic remains safe
Rhombus-like shape	Ensures equal sides without right angles fail

Edge Cases

Duplicate Points

One of the most common bugs is forgetting to reject overlapping points. If two points are identical, the side length becomes zero. A naive implementation that only checks equality of distances could incorrectly classify such a shape as a square.

This implementation explicitly checks:

distances[0] > 0

Since the smallest distance corresponds to a side length, this guarantees every side has positive length.

Rectangle but Not Square

A rectangle has equal diagonals and right angles, but adjacent sides are not equal unless it is specifically a square. Some incorrect solutions only verify diagonal equality and perpendicularity.

The pairwise distance method avoids this issue because a rectangle produces two different side lengths. After sorting, the first four distances will not all match, causing the algorithm to return false.

Rotated Squares

A square may appear rotated relative to the coordinate axes. Solutions that assume horizontal and vertical edges can fail on these inputs.

This implementation is completely orientation-independent because it relies only on distances between points. Distances remain unchanged under rotation, so rotated squares are handled naturally and correctly.