List Point Pairs Spanning Non-Degenerate Boxes in N Dimensions, Sorted by Volume

You are given n points in d-dimensional space; point i (0-based) has integer coordinates points[i]. Any two points i < j define an axis-aligned box that has the two points as opposite corners. The box's volume is the product, over all d axes, of the absolute difference between the two points' coordinates on that axis. In two dimensions the box is a rectangle and its volume is the rectangle's area; the same function must work for every dimension d in the stated range.

Return every pair of points whose box has a non-zero volume, together with that volume.

Function Signature

def box_volumes(points: List[List[int]]) -> List[List[int]]:

Rules

• Each reported pair is a list [i, j, volume] with i < j, where i and j are indices into points.
• A pair whose volume is 0 (the two points share a coordinate on at least one axis, including identical points) is not reported.
• Order the result by volume descending; break ties by i ascending, then by j ascending.
• Return an empty list when no pair qualifies.

Constraints

• 1 <= n <= 300
• 2 <= d <= 6, and every point has exactly d coordinates
• -100 <= points[i][k] <= 100
• Every volume is at most 200^6 = 6.4 * 10^13, which fits in a 64-bit integer and stays below 2^53

Examples

Example 1

points = [[1, 1], [4, 3], [1, 5], [3, 0]]
output = [[2, 3, 10], [0, 1, 6], [1, 2, 6], [1, 3, 3], [0, 3, 2]]

Points 0 and 2 share the x-coordinate 1, so their rectangle has zero area and is left out. Pairs (0, 1) and (1, 2) both have area 6 and are ordered by their first index.

Example 2

points = [[0, 0, 0], [2, 3, 1], [2, 1, 4]]
output = [[0, 2, 8], [0, 1, 6]]

Points 1 and 2 share the first coordinate, so their box is flat and is left out.

Example 3

points = [[5, 5]]
output = []