How do you solve Valid Square on LeetCode?

Valid Square (LeetCode #593) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: A square has four equal sides and two equal diagonals.

What is the brute force solution for Valid Square?

The brute force approach for Valid Square is Brute Force, with O(n²) time complexity and O(1) space complexity. To determine if four points form a square, we can calculate the distances between all pairs of points. A square will have four equal sides and two equal diagonals. By checking these distances, we can confirm if the points form a square. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Valid Square?

Valid Square uses the following concepts: Math, Geometry. The recommended patterns to study are: Hash Set, Geometry.

What are the interview tips for Valid Square?

Always clarify the problem constraints and edge cases. Think about geometric properties that can simplify calculations. Discuss your thought process and approach before jumping into coding.

What are common mistakes when solving Valid Square?

Forgetting to check that the distances are positive (sides cannot be zero). Not considering the order of distances when checking for equal sides and diagonals.

#593

Valid Square

Medium

MathGeometryHash SetGeometry

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of calculating all distances, we can use the properties of a square. A square has equal sides and equal diagonals. We can check the conditions directly using a set to track unique distances.

⚙️

Algorithm

3 steps

1Step 1: Calculate the squared distances for each pair of points and store them in a set.
2Step 2: Ensure the set contains exactly two unique distances: one for the sides and one for the diagonals.
3Step 3: Ensure that the smaller distance appears exactly 4 times (sides) and the larger distance appears exactly 2 times (diagonals).

solution.py10 lines

1# Full working Python code
2from itertools import combinations
3
4def validSquare(p1, p2, p3, p4):
5    points = [p1, p2, p3, p4]
6    distances = set()
7    for (x1, y1), (x2, y2) in combinations(points, 2):
8        dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
9        distances.add(dist)
10    return len(distances) == 2 and 0 not in distances and all(distances.count(d) == 4 if d < max(distances) else distances.count(d) == 2 for d in distances)

ℹ

Complexity note: This complexity is due to the need to store distances in a set, which allows for constant time checks for unique distances.

1A square has four equal sides and two equal diagonals.
2Using squared distances avoids dealing with floating-point precision issues.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.