Rectangle Mania

Tags

Rectangle Mania

Category

Graphs

Difficulty

Hard

Problem Statement

Given a list of 2D points (with integer coordinates where all points have edges that are parallel to the x and y axes), count the number of rectangles that can be formed using these points as corners. A rectangle is defined by four points forming axis-aligned edges.

Intuition

A rectangle aligned with the axes is uniquely determined by two diagonal corners: the bottom-left (x1, y1) and the top-right (x2, y2), provided x1 < x2 and y1 < y2. If we can verify in O(1) that (x1, y2) and (x2, y1) also exist in the point set, then these four points form a rectangle. We simply enumerate all valid pairs of diagonal corners.

Approach

  1. Store all points in a hash set for O(1) lookup.
  2. For every pair of points (x1, y1) and (x2, y2):
    • Check if they can be opposite diagonal corners: x1 < x2 and y1 < y2.
    • Check if the other two corners (x1, y2) and (x2, y1) exist in the set.
    • If yes, increment the rectangle count.
  3. Return the count.

Pseudocode

function rectangleMania(points):
    pointSet = set of (x, y) tuples from points
    count = 0

    for i from 0 to length(points)-1:
        for j from i+1 to length(points)-1:
            (x1, y1) = points[i]
            (x2, y2) = points[j]

            // Ensure they form a valid diagonal (not on same row/column)
            if x1 == x2 or y1 == y2:
                continue

            // Normalize so x1 < x2 and y1 < y2
            // (only count each rectangle once by requiring specific ordering)
            if (min(x1,x2), min(y1,y2)) != (x1, y1) if we want to avoid double counting
                // Alternative: just check both other corners exist and divide by 2

            if (x1, y2) in pointSet and (x2, y1) in pointSet:
                count += 1

    return count / 2    // each rectangle is found twice (once per diagonal pair)

Cleaner version avoiding division:

function rectangleMania(points):
    pointSet = set of (x, y) tuples
    count = 0

    for i from 0 to n-1:
        for j from i+1 to n-1:
            (x1, y1) = points[i]
            (x2, y2) = points[j]
            if x1 != x2 and y1 != y2:
                if (x1, y2) in pointSet and (x2, y1) in pointSet:
                    count += 1

    return count / 2

Time & Space Complexity

MeasureComplexityJustification
TimeO(n^2)Enumerate all pairs of points; each lookup is O(1)
SpaceO(n)Hash set of all points

Key Insights

  • The axis-aligned constraint is crucial. Without it, we would need to verify parallelism and equal lengths, which is significantly harder.
  • Each rectangle is counted twice in the pair enumeration (once for each diagonal), hence the division by 2. Alternatively, enforce an ordering like x1 < x2 and y1 < y2 to count each rectangle exactly once.
  • An alternative approach groups points by x-coordinate or y-coordinate and only checks pairs of points on the same vertical/horizontal line, then looks for the complementary pair. This can be faster in practice when points are sparse.

Edge Cases

  • Fewer than 4 points: no rectangle is possible; return 0.
  • All points on the same line: no rectangle; return 0.
  • Points forming a perfect grid: many rectangles; the formula for an m x n grid is C(m,2) * C(n,2).
  • Duplicate points: depending on the problem definition, deduplicate first.
  • Negative coordinates: the algorithm handles them naturally since it only uses equality and inequality checks.

Linked mentions