Watch the video solution for Rectangles Area, a medium level problem involving Database. This walkthrough by Everyday Data Science has 2,175 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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.
Problem Overview: A table stores 2D points with coordinates (x, y). You need to identify rectangles whose sides are parallel to the axes and compute their area. A valid rectangle requires four points: bottom-left, bottom-right, top-left, and top-right.
Approach 1: Self Join with EXISTS Validation (O(n2) time, O(1) extra space)
The key observation: two points can act as diagonal corners of an axis-aligned rectangle if one is bottom-left and the other is top-right. For points p1(x1, y1) and p2(x2, y2), this condition holds when x1 < x2 and y1 < y2. If those are the diagonal corners, the other two corners must be (x1, y2) and (x2, y1). A SQL SELF JOIN enumerates candidate diagonal pairs, and two EXISTS checks verify the presence of the remaining corners.
The rectangle area is computed using (x2 - x1) * (y2 - y1). Because the query compares each point with others, the dominant cost comes from pair generation via the join, giving O(n2) time complexity. The query itself uses constant additional memory because the database engine streams rows during evaluation.
This pattern appears frequently in database problems where relationships between rows must be discovered without explicit adjacency structures. Using a SQL self-join effectively simulates pairwise comparison, while EXISTS ensures the rectangle is fully formed.
Recommended for interviews: The self-join with EXISTS approach is the expected solution. It demonstrates you understand relational operations like pair generation, filtering with coordinate constraints, and validating conditions using subqueries. Interviewers want to see correct join conditions (x1 < x2, y1 < y2) and the logic that checks the other two corners.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join + EXISTS Validation | O(n^2) | O(1) | Standard SQL solution when detecting rectangles from coordinate points |
| Self Join with Direct Joins for Corners | O(n^2) | O(1) | Alternative query structure using multiple joins instead of EXISTS checks |