LeetCode 1459 - Rectangles Area

LeetCode Problem 1459

Difficulty: 🟡 Medium
Topics: Database

Solution

You included two different problems in one message, and the second prompt supersedes the first. I will provide the detailed technical solution guide for LeetCode 1459 - Rectangles Area following your exact formatting requirements.

Problem Understanding

This problem asks us to identify all possible axis-aligned rectangles that can be formed using pairs of points from a database table. Each point in the Points table represents a coordinate in a two-dimensional plane, with an x_value and a y_value.

The key observation is that each rectangle is defined by two opposite corner points. Since the rectangle must be axis-aligned, its sides must be parallel to the x-axis and y-axis. This means the two opposite corners must differ in both their x-coordinate and y-coordinate. If either coordinate is identical, the rectangle would collapse into a line segment and have zero area, which is explicitly invalid.

The input consists of a database table named Points with three columns:

Column	Meaning
id	Unique identifier for a point
x_value	X coordinate
y_value	Y coordinate

The output should contain:

Column	Meaning
p1	First point id
p2	Second point id
area	Rectangle area

The rectangle area is computed as:

$$|x_1 - x_2| \times |y_1 - y_2|$$

The result must satisfy three ordering conditions:

1. Sort by area in descending order.
2. If areas are equal, sort by p1 in ascending order.
3. If there is still a tie, sort by p2 in ascending order.

An important subtlety is that we only want unique pairs of opposite corners. Since (p1, p2) and (p2, p1) represent the same rectangle, we should only count each pair once. A common strategy is enforcing p1.id < p2.id.

There are several important edge cases. If two points share the same x-coordinate, the width becomes zero, producing a zero-area rectangle that must be excluded. Similarly, if two points share the same y-coordinate, the height becomes zero and the rectangle is invalid. The problem guarantees unique point identifiers, but coordinates themselves may repeat across rows.

Approaches

Brute Force Approach

A naive approach would consider every possible pair of points and determine whether they can form an axis-aligned rectangle.

For every pair (point1, point2), we calculate:

• Width: abs(x1 - x2)
• Height: abs(y1 - y2)

If both values are non-zero, then the pair defines opposite corners of a valid rectangle.

This approach is correct because every valid rectangle must be determined by exactly one pair of diagonal corners. By checking every pair, we guarantee that no valid rectangle is missed.

However, without careful filtering, we would generate duplicate results because (A, B) and (B, A) represent the same rectangle. We solve this by restricting the search to pairs where p1.id < p2.id.

Even though this sounds brute force, it is already efficient enough because checking all pairs of points requires only quadratic time.

Key Insight for an Efficient Solution

The important observation is that we do not need any sophisticated geometry algorithm. Every rectangle is uniquely determined by choosing two opposite corners.

Since we only care about axis-aligned rectangles, validity becomes extremely simple:

• x-values must differ
• y-values must differ

This turns the problem into a self join problem in SQL.

We can join the Points table with itself, enforce p1.id < p2.id to avoid duplicates, filter out zero-area rectangles, compute the area directly, and sort according to the required ordering.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every pair of points
Optimal SQL Self Join	O(n²)	O(1)	Uses self join with filtering and sorting

In practice, both approaches are essentially the same idea. The optimal SQL formulation simply expresses the pairwise comparison efficiently using relational operations.

Algorithm Walkthrough

1. Perform a self join on the Points table.

We join the table with itself because we need to compare every point against every other point. 2. Restrict pairs using p1.id < p2.id.

This ensures each rectangle is counted only once. Without this restriction, (1,2) and (2,1) would both appear, causing duplicates. 3. Filter out invalid rectangles.

We only keep pairs where:

• p1.x_value != p2.x_value
• p1.y_value != p2.y_value

If either coordinate matches, the rectangle has zero width or height, making the area zero. 4. Compute the rectangle area.

Use:

ABS(p1.x_value - p2.x_value) *
ABS(p1.y_value - p2.y_value)

The absolute value guarantees a positive area regardless of point ordering. 5. Return the required columns.

Select:

• p1.id AS p1
• p2.id AS p2
• computed area

6. Sort the results.

Order by:

• area DESC
• p1 ASC
• p2 ASC

Why it works

The algorithm works because every axis-aligned rectangle is uniquely identified by a pair of opposite corners whose x and y coordinates differ. By considering all unique pairs of points and filtering out degenerate cases with zero width or height, we enumerate exactly all valid rectangles. The ordering step ensures the output satisfies the problem requirements.

SQL Solution

SELECT
    p1.id AS p1,
    p2.id AS p2,
    ABS(p1.x_value - p2.x_value) *
    ABS(p1.y_value - p2.y_value) AS area
FROM Points p1
JOIN Points p2
    ON p1.id < p2.id
WHERE p1.x_value != p2.x_value
  AND p1.y_value != p2.y_value
ORDER BY area DESC, p1 ASC, p2 ASC;

The solution starts by joining the Points table with itself. Using p1.id < p2.id prevents duplicate rectangle representations and avoids pairing a point with itself.

The WHERE clause removes invalid rectangles that would have zero area due to matching x-values or y-values.

The area calculation uses the absolute difference between x-coordinates multiplied by the absolute difference between y-coordinates. Finally, the results are sorted according to the required ordering rules.

Worked Example

Consider the following table:

id	x_value	y_value
1	2	7
2	4	8
3	2	10

Step 1: Generate Unique Pairs

Because of p1.id < p2.id, we generate:

p1	p2
1	2
1	3
2	3

Step 2: Validate Rectangles

Pair	x Different?	y Different?	Valid?
(1,2)	Yes	Yes	Yes
(1,3)	No	Yes	No
(2,3)	Yes	Yes	Yes

Pair (1,3) is invalid because both points have the same x-coordinate, resulting in zero width.

Step 3: Compute Area

p1	p2	Formula	Area
1	2	|2−4| × |7−8|	2
2	3	|4−2| × |8−10|	4

Step 4: Sort Results

Descending by area:

p1	p2	area
2	3	4
1	2	2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Self join compares all unique pairs of points
Space	O(1)	No additional data structures are used

The dominant cost comes from the self join, which conceptually compares every point against every other point. Since there are approximately n(n−1)/2 unique pairs, the runtime is quadratic. The extra memory usage is constant because we only compute values directly during query execution.

Test Cases

def rectangles_area(points):
    result = []

    n = len(points)

    for i in range(n):
        for j in range(i + 1, n):
            id1, x1, y1 = points[i]
            id2, x2, y2 = points[j]

            if x1 != x2 and y1 != y2:
                area = abs(x1 - x2) * abs(y1 - y2)
                result.append((id1, id2, area))

    result.sort(key=lambda x: (-x[2], x[0], x[1]))
    return result

# Example 1
assert rectangles_area([
    (1, 2, 7),
    (2, 4, 8),
    (3, 2, 10)
]) == [
    (2, 3, 4),
    (1, 2, 2)
]  # provided example

# Two points with same x-coordinate
assert rectangles_area([
    (1, 5, 1),
    (2, 5, 8)
]) == []  # zero width rectangle

# Two points with same y-coordinate
assert rectangles_area([
    (1, 2, 3),
    (2, 7, 3)
]) == []  # zero height rectangle

# Single valid rectangle
assert rectangles_area([
    (1, 1, 1),
    (2, 4, 5)
]) == [
    (1, 2, 12)
]  # simple valid rectangle

# Multiple rectangles with tie area
assert rectangles_area([
    (1, 0, 0),
    (2, 2, 2),
    (3, 4, 1)
]) == [
    (1, 3, 4),
    (1, 2, 4),
    (2, 3, 2)
]  # ordering by p1 and p2

# Negative coordinates
assert rectangles_area([
    (1, -2, -3),
    (2, 4, 5)
]) == [
    (1, 2, 48)
]  # absolute difference handling

Test Summary

Test	Why
Provided example	Verifies correctness against official output
Same x-coordinate	Ensures zero-width rectangles are excluded
Same y-coordinate	Ensures zero-height rectangles are excluded
Single rectangle	Validates basic area calculation
Equal area ties	Confirms sorting order rules
Negative coordinates	Verifies absolute difference logic

Edge Cases

Points Sharing the Same X Coordinate

If two points have the same x-coordinate, the rectangle width becomes zero. A naive implementation might accidentally include such cases if it only computes area without validation. The solution explicitly filters using p1.x_value != p2.x_value, preventing invalid rectangles.

Points Sharing the Same Y Coordinate

Similarly, identical y-coordinates produce zero height. This is another common source of bugs because the pair still looks geometrically valid at first glance. The query excludes these cases with p1.y_value != p2.y_value.

Duplicate Rectangle Generation

Without restricting pairs to p1.id < p2.id, the same rectangle would appear twice, once as (A,B) and once as (B,A). This would produce incorrect output and potentially break ordering expectations. The implementation guarantees uniqueness by always selecting the smaller id first.

Negative Coordinates

Coordinates may be negative, which can cause incorrect area calculations if subtraction is used directly. Using ABS(x1 - x2) and ABS(y1 - y2) guarantees the area remains positive regardless of point ordering or coordinate sign.