Largest axis-aligned rectangle from points

You are given a list of distinct points on a 2D integer grid. Each point is a pair [x, y].

Return the largest area of a rectangle whose sides are parallel to the x and y axes and whose four corners are all points in the list. Other points may lie inside the rectangle or on its edges. If no such rectangle exists, return 0.

Implement:

def largest_rectangle_area(points: list[list[int]]) -> int: ...

Constraints

• 0 <= len(points) <= 2000
• -10^9 <= x, y <= 10^9
• Points are distinct.

Example 1

Input:  [[0,0],[0,1],[1,0],[1,1],[4,0],[4,1]]
Output: 4

Three rectangles exist: x in [0,1] (area 1), x in [1,4] (area 3) and x in [0,4] (area 4). The largest is 4.

Example 2

Input:  [[0,0],[1,1],[2,2],[3,0]]
Output: 0

No four points form an axis-aligned rectangle.

Start with a straightforward solution, then improve it. Be ready to discuss what changes if the rectangle must contain no other point.