1class Solution {
2    /**
3     * Computes the maximum area of an axis-aligned right triangle that can be
4     * formed using the given points, where one leg of the triangle is parallel
5     * to one of the coordinate axes.
6     *
7     * The approach is run twice: once with the original coordinates, and once
8     * with x and y swapped. Swapping the axes lets us reuse the same logic
9     * (which fixes one axis and varies the other) to cover both orientations.
10     *
11     * @param coords array of points, each represented as [x, y]
12     * @return the maximum triangle area, or -1 if no valid triangle exists
13     */
14    public long maxArea(int[][] coords) {
15        // First pass: treat x as the "grouping" axis.
16        long ans = calc(coords);
17
18        // Swap x and y in every point so the second pass handles the other axis.
19        for (int[] c : coords) {
20            int tmp = c[0];
21            c[0] = c[1];
22            c[1] = tmp;
23        }
24
25        // Second pass with swapped coordinates.
26        ans = Math.max(ans, calc(coords));
27
28        // A valid (positive) area means a triangle exists; otherwise return -1.
29        return ans > 0 ? ans : -1;
30    }
31
32    /**
33     * Calculates the maximum triangle area for the current orientation.
34     *
35     * For each distinct x value, we look at the vertical extent (the difference
36     * between the maximum and minimum y at that x). This vertical segment forms
37     * one leg of the right triangle. The other leg is the horizontal distance
38     * from x to the farthest x boundary (either the global min or max x).
39     * The area is half the product of the two legs; since the formula keeps
40     * d * base, the factor of 1/2 is implicitly handled by the problem's
41     * definition of area being measured this way.
42     *
43     * @param coords array of points, each represented as [x, y]
44     * @return the maximum area found, or 0 if none
45     */
46    private long calc(int[][] coords) {
47        // Global minimum and maximum x across all points.
48        int min = Integer.MAX_VALUE;
49        int max = 0;
50
51        // For each x: minY maps x -> minimum y, maxY maps x -> maximum y.
52        Map<Integer, Integer> minY = new HashMap<>();
53        Map<Integer, Integer> maxY = new HashMap<>();
54
55        for (int[] c : coords) {
56            int x = c[0];
57            int y = c[1];
58
59            // Track the overall horizontal range.
60            min = Math.min(min, x);
61            max = Math.max(max, x);
62
63            // Update the vertical extent recorded for this x value.
64            if (minY.containsKey(x)) {
65                minY.put(x, Math.min(minY.get(x), y));
66                maxY.put(x, Math.max(maxY.get(x), y));
67            } else {
68                minY.put(x, y);
69                maxY.put(x, y);
70            }
71        }
72
73        long ans = 0;
74        // Iterate over every distinct x that has at least one point.
75        for (Map.Entry<Integer, Integer> entry : minY.entrySet()) {
76            int x = entry.getKey();
77            int y = entry.getValue();
78
79            // Vertical leg length: difference between max and min y at this x.
80            int d = maxY.get(x) - y;
81
82            // Horizontal leg length: farthest distance from x to a boundary.
83            ans = Math.max(ans, (long) d * Math.max(max - x, x - min));
84        }
85        return ans;
86    }
87}
88

1class Solution {
2public:
3    long long maxArea(vector<vector<int>>& coords) {
4        // Lambda that computes the maximum rectangle area for the current orientation.
5        // For a fixed x-coordinate, two points sharing that x define a vertical edge
6        // (height = max_y - min_y). The opposite edge can be placed at the farthest
7        // x-coordinate (either the global minimum or maximum x), giving the width.
8        auto calc = [&]() -> long long {
9            int minX = INT_MAX, maxX = 0;
10
11            // minYByX: minimum y observed for each x-coordinate.
12            // maxYByX: maximum y observed for each x-coordinate.
13            unordered_map<int, int> minYByX, maxYByX;
14
15            // First pass: collect global x-range and per-x y-range.
16            for (auto& point : coords) {
17                int x = point[0], y = point[1];
18                minX = min(minX, x);
19                maxX = max(maxX, x);
20                if (minYByX.count(x)) {
21                    minYByX[x] = min(minYByX[x], y);
22                    maxYByX[x] = max(maxYByX[x], y);
23                } else {
24                    minYByX[x] = y;
25                    maxYByX[x] = y;
26                }
27            }
28
29            long long best = 0;
30            // For each distinct x, the vertical edge height is the y-span at that x.
31            // The width is the larger horizontal distance to the global x bounds.
32            for (auto& [x, minY] : minYByX) {
33                int height = maxYByX[x] - minY;
34                int width = max(maxX - x, x - minX);
35                best = max(best, 1LL * height * width);
36            }
37            return best;
38        };
39
40        // Compute the answer with the original orientation.
41        long long ans = calc();
42
43        // Swap x and y of every point to evaluate the transposed orientation,
44        // which covers rectangles whose fixed edge is horizontal instead of vertical.
45        for (auto& point : coords) {
46            swap(point[0], point[1]);
47        }
48        ans = max(ans, calc());
49
50        // A valid rectangle requires a positive area; otherwise return -1.
51        return ans > 0 ? ans : -1;
52    }
53};
54

1/**
2 * Computes the maximum area of an axis-aligned right triangle that can be
3 * formed from the given points, where the right-angle legs are parallel to
4 * the axes. Returns -1 if no valid triangle exists.
5 *
6 * @param coords - Array of [x, y] points.
7 * @returns The maximum triangle area (doubled, since the 1/2 factor is omitted), or -1.
8 */
9function maxArea(coords: number[][]): number {
10    /**
11     * For the current orientation of the points, find the best triangle whose
12     * vertical leg lies on a shared x-coordinate. The two points sharing an x
13     * value provide the vertical side; the horizontal distance to the farthest
14     * x boundary provides the base.
15     */
16    function calc(): number {
17        // Track the global minimum and maximum x-coordinates.
18        let minX = Infinity;
19        let maxX = 0;
20
21        // For each x: minY stores the smallest y, maxY stores the largest y.
22        const minYByX = new Map<number, number>();
23        const maxYByX = new Map<number, number>();
24
25        for (const [x, y] of coords) {
26            minX = Math.min(minX, x);
27            maxX = Math.max(maxX, x);
28
29            if (minYByX.has(x)) {
30                // Update the existing y-range for this x-coordinate.
31                minYByX.set(x, Math.min(minYByX.get(x)!, y));
32                maxYByX.set(x, Math.max(maxYByX.get(x)!, y));
33            } else {
34                // First point seen at this x-coordinate.
35                minYByX.set(x, y);
36                maxYByX.set(x, y);
37            }
38        }
39
40        let best = 0;
41        for (const [x, low] of minYByX) {
42            // Height of the vertical leg at this x-coordinate.
43            const height = maxYByX.get(x)! - low;
44            // Base is the horizontal distance to the farthest boundary.
45            const base = Math.max(maxX - x, x - minX);
46            best = Math.max(best, height * base);
47        }
48        return best;
49    }
50
51    // First pass: vertical legs (shared x-coordinates).
52    let ans = calc();
53
54    // Swap x and y for every point, then run again to handle horizontal legs.
55    for (const point of coords) {
56        [point[0], point[1]] = [point[1], point[0]];
57    }
58    ans = Math.max(ans, calc());
59
60    // A valid triangle requires a positive area; otherwise return -1.
61    return ans > 0 ? ans : -1;
62}
63