Skip to main content
Talentd

Rectangles Area - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase3 min readAsked at: Twitter
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join + EXISTS ValidationO(n^2)O(1)Standard SQL solution when detecting rectangles from coordinate points
Self Join with Direct Joins for CornersO(n^2)O(1)Alternative query structure using multiple joins instead of EXISTS checks

Video Solution

LeetCode Medium 1459 "Rectangles Area" Twitter Interview SQL Question with Explanation • Everyday Data Science • 2,259 views views

Frequently Asked Questions

Is Rectangles Area easy or hard?
Rectangles Area is considered a Medium-level database problem. The challenge lies in recognizing that two points form a diagonal and that the other two corners must exist in the dataset, then translating that logic into an efficient SQL self-join query.
Rectangles Area Python/Java solution
Because this is a database problem, the expected solution is written in SQL (commonly MySQL). The logic can be replicated in Python or Java by storing points in a set and checking whether the other two rectangle corners exist, but interview platforms typically require a SQL query.
How to solve Rectangles Area in O(n)?
An O(n) solution is generally not achievable in SQL for this problem because you must evaluate relationships between pairs of points. The self-join strategy inherently requires O(n^2) comparisons to determine valid diagonals and verify the remaining corners.
What is the best approach for Rectangles Area?
The best approach uses a SQL self join to enumerate potential diagonal point pairs and EXISTS checks to verify the other two rectangle corners. For points (x1,y1) and (x2,y2), the rectangle is valid when x1 < x2 and y1 < y2 and the points (x1,y2) and (x2,y1) also exist. This approach runs in O(n^2) time due to pair comparisons.
Is Rectangles Area asked at Google/Amazon/Meta?
Database-style coordinate problems and SQL self-join questions appear in interviews at companies like Amazon and Meta. While the exact problem may vary, the core skill tested is writing relational queries that detect patterns across multiple rows.
What data structure is used in Rectangles Area?
The problem uses a relational table containing point coordinates. The solution relies on SQL operations such as self joins, filtering conditions, and EXISTS subqueries rather than traditional in-memory data structures.
What is the time complexity of Rectangles Area?
The typical SQL solution runs in O(n^2) time because each point is compared with other points using a self join. Each candidate pair then performs constant-time existence checks. Space complexity is O(1) since the database engine processes rows without storing large intermediate structures.

Ready to solve this problem?

Practice Rectangles Area with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary