Given the coordinates of four points in 2D space p1, p2, p3, and p4, return true if the four points construct a square.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Constraints

  • p1.length == p2.length == p3.length == p4.length == 2
  • -10^4 <= xi, yi <= 10^4

Thinking Process

Given the coordinates of four points in 2D space p1, p2, p3, and p4, return true if the four points construct a square.

  • Identify the pattern from constraints (sorted? graph? optimal substructure?).
  • Write brute force first mentally, then optimize the bottleneck.
  • Verify edge cases: empty input, single element, duplicates.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Brute force (this problem) Often O(n^2) or O(2^n) O(n) Baseline; clarifies the optimization target
Sort + scan O(n log n) O(1) Pairs, intervals, greedy ordering
Hash map / set O(n) O(n) Frequency, membership, two-sum style
Single-pass linear O(n) O(1) Two pointers, sliding window, Kadane

Solution

Time Complexity: O(1) - Constant time since we only have 4 points
Space Complexity: O(1) - Using a set with at most 2 elements

The key insight is that a valid square has exactly two unique distances:

  1. Side length (appears 4 times - 4 sides)
  2. Diagonal length (appears 2 times - 2 diagonals)

Additionally, we must check that no two points are the same (distance = 0).

class Solution:
    def validSquare(self, p1, p2, p3, p4):
        distances = set()
        points = [p1, p2, p3, p4]

        for i in range(4):
            for j in range(i + 1, 4):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                distSq = dx * dx + dy * dy

                if distSq == 0:
                    return False  # Duplicate points

                distances.add(distSq)

        return len(distances) == 2

Solution Explanation

Approach: Brute force (this problem)

Key idea: Given the coordinates of four points in 2D space p1, p2, p3, and p4, return true if the four points construct a square.

How the code works:

  • Identify the pattern from constraints (sorted? graph? optimal substructure?).
  • Write brute force first mentally, then optimize the bottleneck.
  • Verify edge cases: empty input, single element, duplicates.

Walkthrough — input p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1], expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

| Operation | Time | Space | |———–|——|——-| | Calculate distances | O(1) | O(1) | | Store in set | O(1) | O(1) | | Overall | O(1) | O(1) |

Common Mistakes

  1. Duplicate points: If any two points are the same, return false
  2. Rectangle: Would have 3 unique distances (2 different sides + 1 diagonal)
  3. Rhombus: Would have 2 unique distances but diagonal ≠ side × √2 (but our solution still works)

  4. Degenerate cases: All points collinear or forming other shapes

  5. Not checking for duplicate points: Must return false if distSq == 0
  6. Wrong distance count: Expecting exactly 2 unique distances, not more or less
  7. Using floating point: Using squared distances avoids precision issues
  8. Not considering all pairs: Must check all 6 pairs of points

Alternative Approach: Verify Diagonal Relationship

A more rigorous approach would also verify that diagonal² = 2 × side²:

class Solution:
    def validSquare(self, p1, p2, p3, p4):
        distCount = {}

        points = [p1, p2, p3, p4]

        for i in range(4):
            for j in range(i + 1, 4):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                distSq = dx * dx + dy * dy

                if distSq == 0:
                    return False

                distCount[distSq] = distCount.get(distSq, 0) + 1

        if len(distCount) != 2:
            return False

        side = 0
        diagonal = 0

        for dist, count in distCount.items():
            if count == 4:
                side = dist
            elif count == 2:
                diagonal = dist
            else:
                return False

        return diagonal == 2 * side

However, the simpler solution (checking distances.size() == 2) is sufficient because:

  • If there are exactly 2 unique distances with 4 points
  • And one appears 4 times (sides) and one appears 2 times (diagonals)
  • Then it must be a square (the geometric constraints are satisfied)

Key Takeaways

  • Pattern: Brute force (this problem)
  • Identify the pattern from constraints (sorted? graph? optimal substructure?).
  • Write brute force first mentally, then optimize the bottleneck.

References