Count Squares

Tags

Count Squares

Category

Arrays

Difficulty

Hard

Problem Statement

Given a list of 2D points, count the number of axis-aligned squares that can be formed using four of the given points as vertices. Each square must have sides parallel to the x and y axes.

Intuition

An axis-aligned square is uniquely determined by any two of its diagonally opposite corners. Alternatively, and more efficiently, it is determined by any pair of points that share the same y-coordinate (forming a horizontal side). Given two points on the same horizontal line, the side length is their horizontal distance, and we can check whether the other two corners of the square exist. This avoids checking all 4-point combinations.

Approach

  1. Store all points in a hash set for O(1) lookup.
  2. Iterate through all pairs of points (p1, p2).
  3. For each pair sharing the same y-coordinate (p1.y == p2.y): a. Compute the side length dist = abs(p2.x - p1.x). b. Check if the two points above exist: (p1.x, p1.y + dist) and (p2.x, p2.y + dist). c. If both exist, increment the square count.
  4. Since each square is found twice (once from the bottom side, once from the top side), divide the count by 2 at the end.
  5. Return the final count.

Pseudocode

function countSquares(points):
    pointSet = set of all (x, y) tuples in points
    count = 0

    for i from 0 to length(points) - 1:
        for j from i + 1 to length(points) - 1:
            p1 = points[i]
            p2 = points[j]

            if p1.y != p2.y:
                continue

            dist = abs(p2.x - p1.x)
            if dist == 0:
                continue

            // Check square above
            if (p1.x, p1.y + dist) in pointSet and
               (p2.x, p2.y + dist) in pointSet:
                count++

            // Check square below
            if (p1.x, p1.y - dist) in pointSet and
               (p2.x, p2.y - dist) in pointSet:
                count++

    return count / 2

Time & Space Complexity

  • Time: O(n^2) — We check all pairs of points. Each pair lookup in the hash set is O(1).
  • Space: O(n) — For the hash set storing all points.

Key Insights

  • Restricting to axis-aligned squares simplifies the problem enormously. Only points sharing a y-coordinate can form horizontal edges.
  • Using a hash set for point lookup is essential for efficiency.
  • We divide by 2 because each square is counted once from each of its two horizontal edges.
  • For non-axis-aligned squares, the problem becomes significantly harder and requires checking rotated square candidates.

Edge Cases

  • Fewer than 4 points: no square is possible, return 0.
  • All points on a single line: no square is possible.
  • Duplicate points: depending on problem constraints, may need deduplication.
  • Points forming multiple overlapping squares: each valid set of 4 corners counts as one square.
  • Negative coordinates: handled naturally by the algorithm.

Linked mentions