Given $$$n$$$ $$$(2\le n \le 2\cdot 10^5)$$$ distinct points ($$$-10^9\le p_x, p_y\le 10^9$$$) of a two-dimensional plane, find the maximum area of any possible rectangle identified by pairs of points as opposite angles.

This problem is almost identical to this problem so the following tutorial is also valid for that problem with slight modifications.

Editorial:

First of all I simplify the problem by searching for the maximum area formed only by vertices in upper-left and bottom-right corner, and then, invert all $$$y$$$ coordinate of all points, and repeat the search to consider also the rectangles formed by upper-right and bottom-left points.

Notation:

• Let's call the plane $$$P\subseteq R^2$$$.
• Given $$$p, q \in P$$$, $$$p\le q \iff p_x\le q_x\land p_y\le q_y$$$

Definitions:

• upper-left border= $$${p\in P | \nexists q \text{ s.t. } q_x\le p_x\land q_y\ge p_y}$$$
• bottom-right border is defined similarly
• Let's define $$$f$$$ to be the area of the rectangle identified by $$$p$$$ as upper-left corner and $$$q$$$ as bottom-right corner, so $$$f(p, q \in P)=(p_x-q_x)(p_y-q_y)$$$ (Note that it can be negative)

It can be proved that an optimal (with maximum area) rectangle can be formed with a pair of points $$$(p\in $$$ upper-left border $$$, q \in $$$ bottom-right border $$$)$$$

Theorem:

Given 4 points $$$a,b,c,d\in P$$$ such that $$$a\le b\land c \le d$$$

Proof:

We can use this theorem to optimize our search. We search recursively on ranges of type (upper-left border L, upper-left border R, bottom-right border L, bottom-right border R).

We can maintain a stack/queue of ranges/quadruples to consider, the first range/quadruple is (0, length(upper-left border)-1, 0, length(bottom-right border)-1)

We can use this theorem to split a upper-left border range in a quadruple in half at worst case.

We can do that by taking the middle element in the upper-left border, iterate through the bottom-right border and search for the maximum $$$f$$$, let its index be $$$i$$$.

Then we can split our search considering recursively the ranges (0, m-1, 0, i) and (m+1, length(upper-left border)-1, i, length(bottom-right border)-1).

Now we repeat the process in a similar way until the stack/queue is empty.

The worst case the time complexity is $$$O(nlogn)$$$.

Edge case: when the maximum area given in the first search of an iteration is negative, it can be seen that we can simply split between the last element with the x-coordinate less than the x-coordinate of the middle element and the next element.

Implementation:

func computeLargestRectanglenlogn(points [][2]int) int {
	dist := func(p1, p2 [2]int) int {
		return math.Abs((p1[0] - p2[0]) * (p1[1] - p2[1]))
	}
	helper := func(points [][2]int) int {
		upperLeft := [][2]int{}
		maxYSoFar := int(-1e9 - 1)
		for i := 0; i < len(points); i++ {
			if points[i][1] > maxYSoFar {
				upperLeft = append(upperLeft, points[i])
				maxYSoFar = points[i][1]
			}
		}

		bottomRight := [][2]int{}
		minYSoFar := int(1e9 + 1)
		for i := len(points) - 1; i >= 0; i-- {
			if points[i][1] < minYSoFar {
				bottomRight = append(bottomRight, points[i])
				minYSoFar = points[i][1]
			}
		}
		for i, j := 0, len(bottomRight)-1; i < j; i, j = i+1, j-1 {
			bottomRight[i], bottomRight[j] = bottomRight[j], bottomRight[i]
		}

		type Range struct {
			upperLeftL   int
			upperLeftR   int
			bottomRightL int
			bottomRightR int
		}
		ranges := []Range{{0, len(upperLeft) - 1, 0, len(bottomRight) - 1}}
		maxSoFar := 0
		for len(ranges) != 0 {
			ran := ranges[len(ranges)-1]
			ranges = ranges[:len(ranges)-1]

			m := (ran.upperLeftL + ran.upperLeftR) / 2

			bestIbottomRight := -1
			maxSize := -1
			lastIndexOnTheLeftOfBestBottomRight := ran.bottomRightL - 1
			for i := ran.bottomRightL; i <= ran.bottomRightR; i++ {
				if upperLeft[m][0] > bottomRight[i][0] {
					lastIndexOnTheLeftOfBestBottomRight = i
				} else {
					size := dist(upperLeft[m], bottomRight[i])
					if size > maxSize && upperLeft[m][1] > bottomRight[i][1] {
						maxSize = size
						bestIbottomRight = i
					}
				}
			}

			isValid := func(ran Range) bool {
				return ran.upperLeftL <= ran.upperLeftR && ran.bottomRightL <= ran.bottomRightR
			}

			if bestIbottomRight != -1 {

				maxSoFar = math.Max(maxSoFar, maxSize)

				tmp := Range{ran.upperLeftL, m - 1, ran.bottomRightL, bestIbottomRight}
				if isValid(tmp) {
					ranges = append(ranges, tmp)
				}
				tmp = Range{m + 1, ran.upperLeftR, bestIbottomRight, ran.bottomRightR}
				if isValid(tmp) {
					ranges = append(ranges, tmp)
				}
			} else {
				tmp := Range{ran.upperLeftL, m - 1, ran.bottomRightL, lastIndexOnTheLeftOfBestBottomRight}
				if isValid(tmp) {
					ranges = append(ranges, tmp)
				}
				tmp = Range{m + 1, ran.upperLeftR, lastIndexOnTheLeftOfBestBottomRight + 1, ran.bottomRightR}
				if isValid(tmp) {
					ranges = append(ranges, tmp)
				}
			}
		}
		return maxSoFar
	}

	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0]
	})
	tmp := helper(points)
	for i := 0; i < len(points); i++ {
		points[i] = [2]int{points[i][0], -points[i][1]}
	}
	return math.Max(tmp, helper(points))
}

Alternative solution: https://stackoverflow.com/a/69276749