Solution
Approach 1: Sort by Column
Intuition
Count each rectangle by rightmost edge.
Algorithm
Group the points by x
coordinates, so that we have columns of points. Then, for every pair of points in a column (with coordinates (x,y1)
and (x,y2)
), check for the smallest rectangle with this pair of points as the rightmost edge. We can do this by keeping memory of what pairs of points we've seen before.
Complexity Analysis

Time Complexity: , where is the length of
points
. 
Space Complexity: .
Approach 2: Count by Diagonal
Intuition
For each pair of points in the array, consider them to be the long diagonal of a potential rectangle. We can check if all 4 points are there using a Set.
For example, if the points are (1, 1)
and (5, 5)
, we check if we also have (1, 5)
and (5, 1)
. If we do, we have a candidate rectangle.
Algorithm
Put all the points in a set. For each pair of points, if the associated rectangle are 4 distinct points all in the set, then take the area of this rectangle as a candidate answer.
Complexity Analysis

Time Complexity: , where is the length of
points
. 
Space Complexity: , where is the height of the tree.
Analysis written by: @awice. Approach #1 inspired by: @lee215.