Problem Description

You are given four points in a 2D coordinate plane. Your task is to determine whether these four points form a valid square.

Each point is represented as [x, y] where x and y are the coordinates. The four points can be given in any order - they are not necessarily provided in a sequence that traces the perimeter of the square.

For the four points to form a valid square, they must satisfy two conditions:

1. All four sides must have equal length (and the length must be positive, meaning the points cannot all be the same)
2. All four angles must be 90 degrees (right angles)

The solution uses a helper function check(a, b, c) that verifies if three points form a right angle. It calculates the squared distances between all pairs of the three points:

• d1 = squared distance between points a and b
• d2 = squared distance between points a and c
• d3 = squared distance between points b and c

For three points to form a right angle, two of the distances must be equal (these are the two sides of the right angle), and by the Pythagorean theorem, their sum must equal the third distance (the hypotenuse). The function checks all three possible configurations where different pairs could be the equal sides.

The main solution verifies that all four possible combinations of three points from the four given points form right angles. If all four combinations satisfy the right angle property, and the distances are non-zero, then the four points form a valid square.

Intuition

When we think about what makes a square unique among quadrilaterals, we realize that a square has a very special property: every corner is a right angle, and all sides are equal. This gives us a key insight - if we pick any three vertices of a square, they must form a right-angled triangle (specifically, an isosceles right triangle).

The breakthrough comes from recognizing that we don't need to identify which points are adjacent or diagonal to each other. Instead, we can leverage the fact that in a square, any group of three vertices will always form a right angle at one of the vertices.

To understand why this works, imagine a square ABCD. If we pick any three points, say A, B, and C:

• If B is the corner with the right angle, then AB and BC are the two equal sides of the square, and AC is the diagonal
• The Pythagorean theorem tells us that AB² + BC² = AC²

This relationship holds for every possible combination of three vertices from the square. What's clever about this approach is that it naturally handles the unordered input - we don't need to figure out which point connects to which.

The key mathematical insight is using squared distances instead of actual distances. This avoids dealing with square roots and floating-point precision issues. When checking if three points form a right angle, we look for two equal squared distances (the sides) whose sum equals the third squared distance (the hypotenuse).

By verifying that all four possible combinations of three points satisfy this right-angle property, we ensure that:

1. All corners are 90 degrees (since every combination of three points forms a right angle)
2. All sides are equal (since the equal pairs of distances in each check must be consistent across all checks)

The additional check for non-zero distances (and d1, and d2, etc.) ensures that we don't have duplicate points, which would give us zero distances and a false positive.

Learn more about Math patterns.

Solution Approach

The implementation uses a geometric validation approach based on distance calculations and the Pythagorean theorem.

Core Helper Function - check(a, b, c):

The helper function takes three points and verifies if they form a right angle. Here's how it works:

1. Extract coordinates: Unpack the three points into their x and y coordinates:

   (x1, y1), (x2, y2), (x3, y3) = a, b, c

2. Calculate squared distances: Compute the squared distance between each pair of points:

   • d1 = (x1 - x2)² + (y1 - y2)² - squared distance between points a and b
   • d2 = (x1 - x3)² + (y1 - y3)² - squared distance between points a and c
   • d3 = (x2 - x3)² + (y2 - y3)² - squared distance between points b and c

3. Verify right angle conditions: Check if any configuration forms a right angle by testing three cases:

   • Case 1: d1 == d2 and d1 + d2 == d3 and d1 - Right angle at point a
   • Case 2: d2 == d3 and d2 + d3 == d1 and d2 - Right angle at point b
   • Case 3: d1 == d3 and d1 + d3 == d2 and d1 - Right angle at point c

   Each condition checks:

   • Two distances are equal (the two sides of the square meeting at the right angle)
   • Their sum equals the third distance (Pythagorean theorem for the diagonal)
   • The distance is non-zero (ensuring distinct points)

Main Validation Logic:

The main function validates that all four possible combinations of three points from the given four points form right angles:

return (
    check(p1, p2, p3)  # Check if p1, p2, p3 form a right angle
    and check(p2, p3, p4)  # Check if p2, p3, p4 form a right angle
    and check(p1, p3, p4)  # Check if p1, p3, p4 form a right angle
    and check(p1, p2, p4)  # Check if p1, p2, p4 form a right angle
)

If all four checks pass, it confirms that:

• Every corner of the quadrilateral is a right angle (90 degrees)
• All sides have equal length (enforced by the consistency of equal distances across all checks)
• The points are distinct (non-zero distance checks)

Why This Works:

In a valid square, any three vertices will always form an isosceles right triangle. By ensuring all four possible triplets of vertices satisfy this property, we guarantee that the four points form a square. The algorithm elegantly handles the unordered input without needing to determine the connectivity or sequence of the points.

Time Complexity: O(1) - We perform a fixed number of operations regardless of input Space Complexity: O(1) - We only use a constant amount of extra space

Example Walkthrough

Let's walk through an example with four points: p1 = [0, 0], p2 = [0, 1], p3 = [1, 1], p4 = [1, 0]

These points form a unit square with corners at the origin.

Step 1: Check first triplet (p1, p2, p3)

• Points: [0, 0], [0, 1], [1, 1]
• Calculate squared distances:
  • d1 = (0-0)² + (0-1)² = 1 (between p1 and p2)
  • d2 = (0-1)² + (0-1)² = 2 (between p1 and p3)
  • d3 = (0-1)² + (1-1)² = 1 (between p2 and p3)
• Check conditions:
  • d1 == d3 ✓ (both equal 1)
  • d1 + d3 == d2 ✓ (1 + 1 = 2)
  • d1 > 0 ✓
• This forms a right angle at p2

Step 2: Check second triplet (p2, p3, p4)

• Points: [0, 1], [1, 1], [1, 0]
• Calculate squared distances:
  • d1 = (0-1)² + (1-1)² = 1 (between p2 and p3)
  • d2 = (0-1)² + (1-0)² = 2 (between p2 and p4)
  • d3 = (1-1)² + (1-0)² = 1 (between p3 and p4)
• Check conditions:
  • d1 == d3 ✓ (both equal 1)
  • d1 + d3 == d2 ✓ (1 + 1 = 2)
  • d1 > 0 ✓
• This forms a right angle at p3

Step 3: Check third triplet (p1, p3, p4)

• Points: [0, 0], [1, 1], [1, 0]
• Calculate squared distances:
  • d1 = (0-1)² + (0-1)² = 2 (between p1 and p3)
  • d2 = (0-1)² + (0-0)² = 1 (between p1 and p4)
  • d3 = (1-1)² + (1-0)² = 1 (between p3 and p4)
• Check conditions:
  • d2 == d3 ✓ (both equal 1)
  • d2 + d3 == d1 ✓ (1 + 1 = 2)
  • d2 > 0 ✓
• This forms a right angle at p4

Step 4: Check fourth triplet (p1, p2, p4)

• Points: [0, 0], [0, 1], [1, 0]
• Calculate squared distances:
  • d1 = (0-0)² + (0-1)² = 1 (between p1 and p2)
  • d2 = (0-1)² + (0-0)² = 1 (between p1 and p4)
  • d3 = (0-1)² + (1-0)² = 2 (between p2 and p4)
• Check conditions:
  • d1 == d2 ✓ (both equal 1)
  • d1 + d2 == d3 ✓ (1 + 1 = 2)
  • d1 > 0 ✓
• This forms a right angle at p1

Result: All four triplet checks pass, confirming these four points form a valid square.

Notice how each check identified a different corner with the right angle (p2, p3, p4, and p1 respectively), and in each case, the two equal distances were the sides of the square (length 1) while the longer distance was the diagonal (length √2, or 2 when squared).

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm performs a fixed number of operations regardless of input:

• The check function is called exactly 4 times
• Each check function call:
  • Calculates 3 squared distances (d1, d2, d3), each requiring constant time operations
  • Evaluates 3 boolean conditions in the any() function
  • All arithmetic operations (subtraction, multiplication, addition, comparison) are O(1)
• Total operations: 4 × (3 distance calculations + 3 condition checks) = constant number of operations

Since the number of points is fixed at 4 and all operations are arithmetic comparisons on fixed-size data, the overall time complexity is O(1).

Space Complexity: O(1)

The algorithm uses a constant amount of extra space:

• The check function uses 3 local variables (d1, d2, d3) to store squared distances
• Temporary variables for unpacking coordinates (x1, y1, x2, y2, x3, y3)
• No recursive calls (so no additional stack space beyond function calls)
• No data structures that grow with input size

All space usage is independent of the input size (which is fixed anyway), resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating Point Precision Issues

Pitfall: If you calculate actual distances using square roots instead of squared distances, you may encounter floating-point precision errors when comparing distances for equality.

# WRONG: Using actual distances with square root
import math
d1 = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
d2 = math.sqrt((x1 - x3) ** 2 + (y1 - y3) ** 2)
if d1 == d2:  # May fail due to floating point precision
    # ...

Solution: Always work with squared distances to avoid floating-point operations entirely. Integer arithmetic is exact when coordinates are integers.

# CORRECT: Using squared distances
d1 = (x1 - x2) ** 2 + (y1 - y2) ** 2
d2 = (x1 - x3) ** 2 + (y1 - y3) ** 2
if d1 == d2:  # Exact comparison with integers
    # ...

2. Forgetting to Check for Degenerate Cases

Pitfall: Not verifying that distances are non-zero, which would mean some points are identical.

# WRONG: Missing non-zero check
def check(a, b, c):
    # ... calculate distances ...
    return d1 == d2 and d1 + d2 == d3  # Could be true if all points are the same!

Solution: Always include a check that distances are positive to ensure points are distinct.

# CORRECT: Including non-zero validation
def check(a, b, c):
    # ... calculate distances ...
    return d1 == d2 and d1 + d2 == d3 and d1 > 0  # Ensures distinct points

3. Incorrect Pythagorean Theorem Application

Pitfall: Confusing which distances should be equal and which should be the hypotenuse. Remember that in a right isosceles triangle formed by three vertices of a square, the two equal sides are the square's edges, and the longer side is the diagonal.

# WRONG: Incorrect relationship between distances
if d1 == d3 and d1 == d2:  # This would mean all three distances are equal - not possible in a right triangle!
    return True

Solution: Correctly identify that two distances should be equal (the sides), and their sum should equal the third (the diagonal).

# CORRECT: Proper Pythagorean relationship
if d1 == d2 and d1 + d2 == d3 and d1 > 0:  # Two sides equal, sum equals hypotenuse
    return True

4. Assuming Points are Given in Order

Pitfall: Trying to check adjacent sides or assuming the points form a connected path around the square's perimeter.

# WRONG: Assuming p1->p2->p3->p4 forms the perimeter
side1 = distance(p1, p2)
side2 = distance(p2, p3)
side3 = distance(p3, p4)
side4 = distance(p4, p1)
return side1 == side2 == side3 == side4  # Won't work if points are unordered!

Solution: The provided approach correctly handles unordered points by checking all possible triplet combinations, which works regardless of point ordering.

5. Checking Only Partial Conditions

Pitfall: Verifying only that all sides are equal (rhombus condition) without checking angles, or only checking some triplets instead of all four.

# WRONG: Only checking three out of four triplets
return check(p1, p2, p3) and check(p2, p3, p4) and check(p1, p3, p4)
# Missing check(p1, p2, p4) - could be a non-square quadrilateral!

Solution: Always verify all four triplet combinations to ensure every corner forms a right angle.

# CORRECT: Checking all four combinations
return (check(p1, p2, p3) and check(p2, p3, p4) and 
        check(p1, p3, p4) and check(p1, p2, p4))