#593

Medium

LeetCode Problem Workspace

Valid Square

Determine if four given 2D points form a valid square using geometric distance checks and vector validation techniques.

Problem Statement

You are given four points in 2D space represented as p1, p2, p3, and p4. Each point pi has coordinates [xi, yi]. Determine whether these four points can form a valid square regardless of their order.

A valid square must have four sides of equal positive length and four 90-degree angles. Return true if the points construct such a square, and false otherwise.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Example 3

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

Output: true

Example details omitted.

Constraints

p1.length == p2.length == p3.length == p4.length == 2
-104 <= xi, yi <= 104

Solution Approach

Compute Pairwise Distances

Calculate the squared distances between every pair of points to avoid floating-point errors. Use these distances to identify potential side lengths and diagonals, which is critical because miscalculating distances can falsely indicate a non-square.

Validate Side and Diagonal Counts

Count the frequency of each unique distance. A valid square should have exactly two distinct distances: the smaller one occurring four times for sides and the larger one occurring twice for diagonals. Any deviation immediately rules out a square.

Check for Coinciding Points and Geometry Consistency

Ensure no two points coincide and that the diagonal length is consistent with the side length using the Pythagorean relationship. This step prevents false positives from rectangles or degenerate quadrilaterals.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) because there are always six pairwise distances to compute regardless of input. Space complexity is also O(1) for storing distances and their counts.

What Interviewers Usually Probe

Are all points guaranteed to be distinct and in integer coordinates?
Should we handle floating-point errors or stick to integer arithmetic?
Do we need to verify 90-degree angles explicitly or infer from side and diagonal lengths?

Common Pitfalls or Variants

Common pitfalls

Failing to check that all four sides are positive and equal length.
Assuming the input order represents any specific sequence of vertices.
Using square roots instead of squared distances, causing floating-point inaccuracies.

Follow-up variants

Check if four points form a rectangle instead of a square, focusing on opposite sides equality.
Determine if N points can form a regular polygon using generalized distance patterns.
Validate if four points form a rhombus by verifying equal side lengths but not necessarily right angles.

FAQ

What defines a valid square in the Valid Square problem?

A valid square requires four equal-length sides with positive length and four right angles, independent of point order.

Why compute squared distances instead of actual distances?

Squared distances avoid floating-point errors and maintain integer arithmetic, making side and diagonal comparisons exact.

How can I distinguish a square from a rectangle here?

By counting distance frequencies: squares have exactly four equal sides and two equal diagonals, whereas rectangles have two equal sides and two equal diagonals.

Do the input points need to be in any specific order?

No, the solution must handle any input order by considering all pairwise distances and validating the square geometry.

Can coinciding points form a valid square?

No, any coinciding points mean side lengths are zero, which violates the positive-length requirement for a square.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def validSquare(
        self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]
    ) -> bool:
        def check(a, b, c):
            (x1, y1), (x2, y2), (x3, y3) = a, b, c
            d1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
            d2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3)
            d3 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3)
            return any(
                [
                    d1 == d2 and d1 + d2 == d3 and d1,
                    d2 == d3 and d2 + d3 == d1 and d2,
                    d1 == d3 and d1 + d3 == d2 and d1,
                ]
            )

        return (
            check(p1, p2, p3)
            and check(p2, p3, p4)
            and check(p1, p3, p4)
            and check(p1, p2, p4)
        )

Continue Practicing

#587 erect the fence #478 generate random point in a circle #391 perfect rectangle