Rectangles Area

Problem

Table: Points

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| x_value       | int     |
| y_value       | int     |
+---------------+---------+
id is the column with unique values for this table.
Each point is represented as a 2D coordinate (x_value, y_value).

Write a solution to report all possible axis-aligned rectangles with a non-zero area that can be formed by any two points from the Points table.

Each row in the result should contain three columns (p1, p2, area) where:

p1 and p2 are the id’s of the two points that determine the opposite corners of a rectangle.
area is the area of the rectangle and must be non-zero.

Return the result table ordered by area in descending order. If there is a tie, order them by p1 in ascending order. If there is still a tie, order them by p2 in ascending order.

The result format is in the following table.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1400-1499/1459.Rectangles%20Area/images/rect.png)
Input: 
Points table:
+----------+-------------+-------------+
| id       | x_value     | y_value     |
+----------+-------------+-------------+
| 1        | 2           | 7           |
| 2        | 4           | 8           |
| 3        | 2           | 10          |
+----------+-------------+-------------+
Output: 
+----------+-------------+-------------+
| p1       | p2          | area        |
+----------+-------------+-------------+
| 2        | 3           | 4           |
| 1        | 2           | 2           |
+----------+-------------+-------------+
Explanation: 
The rectangle formed by p1 = 2 and p2 = 3 has an area equal to |4-2| * |8-10| = 4.
The rectangle formed by p1 = 1 and p2 = 2 has an area equal to |2-4| * |7-8| = 2.
Note that the rectangle formed by p1 = 1 and p2 = 3 is invalid because the area is 0.

Solution

Method 1 – Self Join and Area Calculation

Intuition

For every pair of points, if their x and y values are both different, they can form the diagonal of an axis-aligned rectangle. The area is the product of the absolute differences of their x and y values.

Approach

Join the table with itself to get all pairs of points (p1, p2) with p1.id < p2.id.
For each pair, check that both x and y values are different.
Compute the area as |x1 - x2| * |y1 - y2|.
Filter out pairs with area 0.
Order by area descending, then p1 ascending, then p2 ascending.

Code

1
2
3
4
5
6
7
8


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, p2;

1
2
3
4
5
6
7
8


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, p2;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


# df is a pandas DataFrame with columns: id, x_value, y_value
from itertools import combinations
import numpy as np
rows = []
for (i1, x1, y1), (i2, x2, y2) in combinations(df.values, 2):
    if x1 != x2 and y1 != y2:
        area = abs(x1 - x2) * abs(y1 - y2)
        rows.append((i1, i2, area))
result = pd.DataFrame(rows, columns=["p1", "p2", "area"])
result = result.sort_values(["area", "p1", "p2"], ascending=[False, True, True])

Complexity

⏰ Time complexity: O(n^2), where n is the number of points, since we check all pairs.
🧺 Space complexity: O(k), where k is the number of valid rectangle pairs (output size).

Problem#

Examples#

Solution#

Method 1 – Self Join and Area Calculation#

Intuition#

Approach#

Code#

Complexity#