Solution


Approach 1: Sort by Column

Intuition

Count each rectangle by right-most 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.