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.

#593

Medium

auto_awesome数学·结合·几何

LeetCode 题解工作台

有效的正方形

给定2D空间中四个点的坐标 p1 , p2 , p3 和 p4 ，如果这四个点构成一个正方形，则返回 true 。点的坐标 p i 表示为 [xi, yi] 。输入没有任何顺序。一个有效的正方形有四条等边和四个等角(90度角)。示例 1: 输入: p1 = [0,0], p2 = [1…

数学几何

题目描述

给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。

点的坐标 p_i 表示为 [xi, yi] 。 输入没有任何顺序 。

一个 有效的正方形 有四条等边和四个等角(90度角)。

示例 1:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: true

示例 2:

输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

示例 3:

输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true

提示:

p1.length == p2.length == p3.length == p4.length == 2
-10⁴ <= x_i, y_i <= 10⁴

lightbulb

解题思路

方法一：数学

若任选三个点，都能构成等腰直角三角形，说明是有效的正方形。

时间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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)
        )

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#587 安装栅栏 #478 在圆内随机生成点 #391 完美矩形