LeetCode Problem 3588

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Greedy, Geometry, Enumeration

Solution

LeetCode 3588 - Find Maximum Area of a Triangle

Problem Understanding

We are given n distinct points on a 2D Cartesian plane. Each point is represented as [x, y].

We must choose any three points that form a non-degenerate triangle, meaning the area must be strictly greater than zero. Among all valid triangles, we are only interested in triangles where at least one side is parallel to either the x-axis or the y-axis.

The problem asks us to return twice the maximum area of such a triangle.

Returning twice the area is important because the geometric area formula often contains a factor of 1/2. By returning 2 * area, we can work entirely with integers and avoid floating point arithmetic.

For a triangle with:

• horizontal base length = b
• vertical height = h

we have:

$$\text{Area} = \frac{b \cdot h}{2}$$

Therefore:

$$2 \cdot \text{Area} = b \cdot h$$

The constraints are large:

• n ≤ 100000
• coordinates can be as large as 10^6

This immediately rules out any solution that examines all triples of points. Since there are O(n³) possible triangles, a brute force approach would be completely infeasible.

The important observations are:

• A horizontal side requires two points sharing the same y.
• A vertical side requires two points sharing the same x.
• Once a base is fixed, the best third point is the one farthest from the base line.
• Since we only need the maximum area, we do not need to enumerate every possible triangle.

Important edge cases include:

• No two points share an x or a y, making it impossible to create a valid axis-parallel side.
• Multiple points lie on the same horizontal or vertical line.
• A candidate base exists, but every point lies on the same line, producing zero area.
• The optimal triangle may come from either a horizontal base or a vertical base.

Approaches

Brute Force

The most direct solution is to examine every possible triple of points.

For each triple:

1. Check whether any side is horizontal or vertical.
2. Compute the triangle area.
3. Keep the maximum valid area.

This is correct because every possible triangle is considered.

However, there are:

$$\binom{n}{3}$$

possible triples.

For n = 100000, this is astronomically large. Even O(n²) would be too slow, so O(n³) is completely impractical.

Key Insight

Suppose we use a horizontal side as the triangle base.

If two points share the same y coordinate:

$$(x_1, y), (x_2, y)$$

then the base length is:

$$|x_2 - x_1|$$

The height is simply the vertical distance from the third point to the line y:

$$|y_3 - y|$$

To maximize area for a fixed horizontal line y, we should:

• maximize the base length on that line
• maximize the distance to any point in the entire set

For a horizontal line y:

• largest possible base is

$$\max x - \min x$$

among points having that y.

• largest possible height is

$$\max(y - \text{globalMinY}, \text{globalMaxY} - y)$$

because the farthest point from that horizontal line must lie at one of the global vertical extremes.

The same logic applies symmetrically for vertical bases.

For a vertical line x:

• base length is

$$\max y - \min y$$

on that line.

• maximum height is

$$\max(x - \text{globalMinX}, \text{globalMaxX} - x)$$

Thus, after grouping points by x and y, every candidate can be evaluated in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Enumerates every triangle
Optimal	O(n)	O(n)	Uses grouping by x and y and global extrema

Algorithm Walkthrough

1. Compute the global extrema:

• globalMinX
• globalMaxX
• globalMinY
• globalMaxY

These values allow us to instantly determine the maximum possible height for any horizontal or vertical base. 2. Build a hash map keyed by y.

For each horizontal line, store:

• smallest x on that line
• largest x on that line

The difference gives the longest possible horizontal base on that line. 3. Build a hash map keyed by x.

For each vertical line, store:

• smallest y on that line
• largest y on that line

The difference gives the longest possible vertical base on that line. 4. Iterate through every horizontal line.

For a line y:

• base length = maxXOnLine - minXOnLine
• height = max(y - globalMinY, globalMaxY - y)

If both are positive, update the answer with:

$$\text{base} \times \text{height}$$ 5. Iterate through every vertical line.

For a line x:

• base length = maxYOnLine - minYOnLine
• height = max(x - globalMinX, globalMaxX - x)

If both are positive, update the answer with:

$$\text{base} \times \text{height}$$ 6. If no positive area was found, return -1. 7. Otherwise return the maximum value obtained.

Why it works

For any horizontal base on a fixed line y, the area is:

$$\frac{\text{base} \times \text{height}}{2}$$

The largest base available on that line is the distance between the leftmost and rightmost points sharing that y. Any shorter base cannot produce a larger area.

Similarly, the largest possible height from line y is achieved by the point whose y coordinate is farthest from y, which must be either the global minimum y or global maximum y.

Therefore every horizontal line can be optimized independently using only its extrema. The same argument applies to vertical lines. Since every valid triangle must contain either a horizontal or vertical side, the algorithm evaluates the optimal representative for every possible axis-parallel base and therefore finds the global optimum.

Problem Understanding

We are given a finite set of points in the integer lattice of the Cartesian plane. Each point is specified by integer coordinates $(x, y)$, and all points are distinct.

We must choose any three distinct points that form a non-degenerate triangle, with the additional constraint that at least one side of the triangle must be parallel to either the x-axis or the y-axis. For each valid triangle, its area is computed in the usual Euclidean sense, and we are required to return twice the maximum possible area among all valid triangles. Returning twice the area eliminates fractional values since the area of a triangle with integer coordinates and a horizontal or vertical base reduces naturally to an integer expression.

If no triple of points satisfies both the geometric constraint and the non-degeneracy requirement (non-zero area), the function must return $-1$.

The input size constraint $n \le 10^5$ implies that any solution with cubic or quadratic dependence on $n$ is infeasible. We must therefore reduce the problem to near-linear or linearithmic structure, most likely via grouping and extremal preprocessing.

Edge cases include configurations where no two points share the same x-coordinate or y-coordinate, making it impossible to form any axis-parallel side, and configurations where all points are collinear or aligned in a way that yields zero area triangles only. We must also ensure that we reject degenerate cases where the computed area is zero even if a “base” exists.

Approaches

Brute Force Approach

The naive method considers all triples of points $(i, j, k)$, computes the triangle area using the determinant formula, and checks whether at least one of its sides is horizontal or vertical. For each triple, we verify the axis-parallel condition by checking whether any pair among the three points shares the same x-coordinate or y-coordinate.

This approach is correct because it exhaustively enumerates all possible valid triangles. However, its computational cost is prohibitive: there are $\binom{n}{3}$ triples, each requiring constant-time checks and arithmetic, leading to cubic complexity.

Key Insight

The constraint that at least one side is parallel to an axis fundamentally reduces the geometry of valid triangles. If a triangle has a horizontal base, then two vertices share the same y-coordinate. Similarly, a vertical base implies two vertices share the same x-coordinate.

For a horizontal base at level $y$, say between points $(x_1, y)$ and $(x_2, y)$, the doubled area of any triangle formed with a third point $(x_3, y_3)$ is:

$$\text{area} \times 2 = |x_1 - x_2| \cdot |y_3 - y|$$

Thus, for a fixed horizontal base, maximizing area reduces to maximizing the vertical distance from that line. Crucially, this depends only on global extrema of y-values, not on the specific third point.

A symmetric argument applies for vertical bases.

Thus, the problem reduces to:

1. Group points by identical y-values and compute the widest horizontal segment per group.
2. Group points by identical x-values and compute the tallest vertical segment per group.
3. Multiply each base length by the maximum perpendicular span in the entire dataset.

This transforms the problem into linear preprocessing plus group scanning.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(n^3)$	$O(1)$	Enumerates all triples explicitly
Optimal	$O(n)$	$O(n)$	Uses grouping by x and y with global extrema

Algorithm Walkthrough

We now construct the optimal solution rigorously.

1. We first scan all points once to compute four global extrema: minimum and maximum x-values, and minimum and maximum y-values. These values define the maximum possible vertical and horizontal spans in the entire point set. They will later allow us to compute perpendicular heights in constant time.
2. We then build two hash maps. The first groups points by their y-coordinate, storing for each y-value the minimum and maximum x-values among all points on that horizontal line. The second groups points by their x-coordinate, storing for each x-value the minimum and maximum y-values among all points on that vertical line.
3. For each group of points sharing a common y-coordinate, we check whether the group contains at least two points. If so, it defines a valid horizontal segment with base length equal to the difference between its maximum and minimum x-values. The corresponding height is the maximum vertical distance from that y-level to any point in the plane, which is given by:

$$\max(y - \min_y, \max_y - y)$$ 4. For each such horizontal base, we compute a candidate doubled area as:

$$(x_{\max} - x_{\min}) \cdot \max(y - \min_y, \max_y - y)$$ 5. We repeat the symmetric process for each x-group, computing vertical bases and their corresponding horizontal heights:

$$(y_{\max} - y_{\min}) \cdot \max(x - \min_x, \max_x - x)$$ 6. We track the maximum value over all such candidates. 7. If no valid group produces a non-zero area, we return $-1$, since all candidate triangles are degenerate.

Why it works

The correctness follows from a decomposition of all valid triangles by their axis-parallel side. Any valid triangle must contain either a horizontal or vertical base. For a fixed base, the area is maximized by choosing the third point with maximal perpendicular distance from the base line. Since this distance depends only on global extrema, no local combinatorial search is required. Therefore, the optimal triangle must appear among the enumerated group extrema.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxArea(self, coords: List[List[int]]) -> int:
        global_min_x = min(x for x, y in coords)
        global_max_x = max(x for x, y in coords)
        global_min_y = min(y for x, y in coords)
        global_max_y = max(y for x, y in coords)

        y_groups = {}
        x_groups = {}

        for x, y in coords:
            if y not in y_groups:
                y_groups[y] = [x, x]
            else:
                y_groups[y][0] = min(y_groups[y][0], x)
                y_groups[y][1] = max(y_groups[y][1], x)

            if x not in x_groups:
                x_groups[x] = [y, y]
            else:
                x_groups[x][0] = min(x_groups[x][0], y)
                x_groups[x][1] = max(x_groups[x][1], y)

        best = 0

        for y, (min_x, max_x) in y_groups.items():
            base = max_x - min_x
            if base == 0:
                continue

            height = max(
                y - global_min_y,
                global_max_y - y
            )

            if height > 0:
                best = max(best, base * height)

        for x, (min_y, max_y) in x_groups.items():
            base = max_y - min_y
            if base == 0:
                continue

            height = max(
                x - global_min_x,
                global_max_x - x
            )

            if height > 0:
        if len(coords) < 3:
            return -1

        min_x = min_y = float("inf")
        max_x = max_y = float("-inf")

        y_groups = defaultdict(lambda: [float("inf"), float("-inf")])
        x_groups = defaultdict(lambda: [float("inf"), float("-inf")])

        for x, y in coords:
            min_x = min(min_x, x)
            max_x = max(max_x, x)
            min_y = min(min_y, y)
            max_y = max(max_y, y)

            y_groups[y][0] = min(y_groups[y][0], x)
            y_groups[y][1] = max(y_groups[y][1], x)

            x_groups[x][0] = min(x_groups[x][0], y)
            x_groups[x][1] = max(x_groups[x][1], y)

        best = 0

        for y, (mnx, mxx) in y_groups.items():
            if mxx > mnx:
                base = mxx - mnx
                height = max(y - min_y, max_y - y)
                best = max(best, base * height)

        for x, (mny, mxy) in x_groups.items():
            if mxy > mny:
                base = mxy - mny
                height = max(x - min_x, max_x - x)
                best = max(best, base * height)

        return best if best > 0 else -1

The implementation begins by computing the global coordinate extrema. These values allow us to determine the largest possible height for any candidate base in constant time.

Next, two hash maps are constructed. The first groups points by their y coordinate and records the smallest and largest x values on each horizontal line. The second groups points by their x coordinate and records the smallest and largest y values on each vertical line.

After preprocessing, every horizontal line contributes at most one candidate, namely the longest base available on that line combined with the largest possible height. The same process is repeated for vertical lines.

The maximum value encountered is exactly twice the largest triangle area, so it can be returned directly. The implementation first computes global extrema in a single pass. It then builds grouped statistics for each horizontal and vertical line. Each group stores only the necessary extremal coordinates, ensuring constant-time updates per point.

Finally, it evaluates all candidate bases and computes the maximal doubled area directly.

Go Solution

func maxArea(coords [][]int) int64 {
	n := len(coords)

	globalMinX, globalMaxX := coords[0][0], coords[0][0]
	globalMinY, globalMaxY := coords[0][1], coords[0][1]

	for i := 1; i < n; i++ {
		x, y := coords[i][0], coords[i][1]

		if x < globalMinX {
			globalMinX = x
		}
		if x > globalMaxX {
			globalMaxX = x
		}
		if y < globalMinY {
			globalMinY = y
		}
		if y > globalMaxY {
			globalMaxY = y
		}
	}

	yGroups := make(map[int][2]int)
	xGroups := make(map[int][2]int)

	for _, p := range coords {
		x, y := p[0], p[1]

		if v, ok := yGroups[y]; ok {
			if x < v[0] {
				v[0] = x
			}
			if x > v[1] {
				v[1] = x
			}
			yGroups[y] = v
		} else {
			yGroups[y] = [2]int{x, x}
		}

		if v, ok := xGroups[x]; ok {
			if y < v[0] {
				v[0] = y
			}
			if y > v[1] {
				v[1] = y
			}
			xGroups[x] = v
		} else {
			xGroups[x] = [2]int{y, y}
		}
	}

	var best int64 = 0

	for y, v := range yGroups {
		base := v[1] - v[0]
		if base == 0 {
			continue
		}

		height := y - globalMinY
		if globalMaxY-y > height {
			height = globalMaxY - y
		}

		if height > 0 {
			area2 := int64(base) * int64(height)
			if area2 > best {
				best = area2
			}
		}
	}

	for x, v := range xGroups {
		base := v[1] - v[0]
		if base == 0 {
			continue
		}

		height := x - globalMinX
		if globalMaxX-x > height {
			height = globalMaxX - x
		}

		if height > 0 {
			area2 := int64(base) * int64(height)
			if area2 > best {
				best = area2
			}
		}
	}

	if best == 0 {
		return -1
	}

	return best
}

The Go implementation follows the same logic as the Python solution. The primary difference is that map values are stored as fixed-size arrays [2]int, which track the minimum and maximum coordinate values. The result is stored in int64 because coordinate differences can reach 10^6, and their product can reach 10^12, which exceeds the range of a 32-bit integer. if len(coords) < 3 { return -1 }

minX, minY := int64(1<<62), int64(1<<62)
maxX, maxY := int64(-1<<62), int64(-1<<62)

type pair struct{ mn, mx int64 }

yMap := make(map[int64]pair)
xMap := make(map[int64]pair)

for _, p := range coords {
    x := int64(p[0])
    y := int64(p[1])

    if x < minX {
        minX = x
    }
    if x > maxX {
        maxX = x
    }
    if y < minY {
        minY = y
    }
    if y > maxY {
        maxY = y
    }

    if v, ok := yMap[y]; ok {
        if x < v.mn {
            v.mn = x
        }
        if x > v.mx {
            v.mx = x
        }
        yMap[y] = v
    } else {
        yMap[y] = pair{x, x}
    }

    if v, ok := xMap[x]; ok {
        if y < v.mn {
            v.mn = y
        }
        if y > v.mx {
            v.mx = y
        }
        xMap[x] = v
    } else {
        xMap[x] = pair{y, y}
    }
}

var best int64 = 0

for y, v := range yMap {
    if v.mx > v.mn {
        base := v.mx - v.mn
        height := max(y-minY, maxY-y)
        area := base * height
        if area > best {
            best = area
        }
    }
}

for x, v := range xMap {
    if v.mx > v.mn {
        base := v.mx - v.mn
        height := max(x-minX, maxX-x)
        area := base * height
        if area > best {
            best = area
        }
    }
}

if best == 0 {
    return -1
}
return best

}

func max(a, b int64) int64 { if a > b { return a } return b }

In Go, explicit handling of integer types is required to avoid overflow and maintain consistency, so all coordinate arithmetic is promoted to `int64`. Maps store only extremal pairs for each key. The logic mirrors the Python implementation exactly, with manual updates to min/max values inside map entries due to Go’s value-copy semantics.

## Worked Examples

### Example 1

Input:

[[1,1],[1,2],[3,2],[3,3]]

Global extrema:

| Variable | Value |
| --- | --- |
| globalMinX | 1 |
| globalMaxX | 3 |
| globalMinY | 1 |
| globalMaxY | 3 |

#### Build y-groups

| y | minX | maxX |
| --- | --- | --- |
| 1 | 1 | 1 |
| 2 | 1 | 3 |
| 3 | 3 | 3 |

For `y = 2`:

| Quantity | Value |
| --- | --- |
| Base | 3 - 1 = 2 |
| Height | max(2 - 1, 3 - 2) = 1 |
| Area × 2 | 2 |

Current best = 2.

#### Build x-groups

| x | minY | maxY |
| --- | --- | --- |
| 1 | 1 | 2 |
| 3 | 2 | 3 |

For `x = 1`:

| Quantity | Value |
| --- | --- |
| Base | 1 |
| Height | 2 |
| Area × 2 | 2 |

Best remains 2.

Final answer:

2

$$[(1,1),(1,2),(3,2),(3,3)]$$

Global extrema:

$$\min x = 1,\ \max x = 3,\ \min y = 1,\ \max y = 3$$

Horizontal groups:

- y = 2 → x values {1, 3}, base = 2

height = max(2 - 1, 3 - 2) = 1

area = 2 × 1 = 2

Vertical groups:

- x = 1 → y values {1, 2}, base = 1

height = max(1, 2) = 2

area = 2
- x = 3 → y values {2, 3}, base = 1

height = max(2, 1) = 2

area = 2

Maximum doubled area = 2.

Output: 2

### Example 2

Input:

[[1,1],[2,2],[3,3]]

Every `y` group contains exactly one point.

| y | minX | maxX |
| --- | --- | --- |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |

All horizontal bases have length 0.

Every `x` group also contains exactly one point.

| x | minY | maxY |
| --- | --- | --- |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |

All vertical bases have length 0.

No valid triangle exists.

Answer:

-1

$$[(1,1),(2,2),(3,3)]$$

No two points share x or y, so no valid base exists.

Best remains 0 → return -1.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | One pass for extrema, one pass for grouping, one pass over groups |
| Space | O(n) | Hash maps may contain up to n distinct x and y values |

The algorithm performs only a constant amount of work per point. The number of distinct `x` groups plus distinct `y` groups is at most `2n`, so all later processing remains linear. This easily satisfies the constraint of `100000` points.
| Time | $O(n)$ | Each point is processed once for grouping and once during evaluation |
| Space | $O(n)$ | Hash maps store at most one entry per distinct x and y value |

The linear complexity arises from the fact that all geometric reductions are precomputed into constant-time extremal queries per group.

## Test Cases

sol = Solution()

assert sol.maxArea([[1,1],[1,2],[3,2],[3,3]]) == 2 # example 1

assert sol.maxArea([[1,1],[2,2],[3,3]]) == -1 # example 2

assert sol.maxArea([[1,1],[5,1],[3,4]]) == 12 # simple horizontal base

assert sol.maxArea([[2,1],[2,6],[7,3]]) == 25 # simple vertical base

assert sol.maxArea([[1,1],[10,1]]) == -1 # only two points

assert sol.maxArea([[1,1],[5,1],[9,1]]) == -1 # all points on one line

assert sol.maxArea([[1,1],[10,1],[5,20]]) == 171 # large height

assert sol.maxArea([[1,1],[1,10],[20,5]]) == 171 # large width

assert sol.maxArea([[1,5],[10,5],[1,1],[1,20]]) == 171 # both orientations available

assert sol.maxArea([[1,1],[1000000,1],[500000,1000000]]) == 999999 * 999999 # large coordinates

assert sol.maxArea([[1,2],[5,2],[9,2],[3,10]]) == 64 # choose widest horizontal base

assert sol.maxArea([[2,1],[2,5],[2,9],[10,4]]) == 64 # choose tallest vertical base

### Test Summary

| Test | Why |
| --- | --- |
| Example 1 | Verifies standard valid triangle |
| Example 2 | No axis-parallel side exists |
| Single horizontal base | Basic correctness |
| Single vertical base | Symmetric correctness |
| Two points only | Cannot form a triangle |
| Collinear points | Zero area must be rejected |
| Large height | Tests height computation |
| Large width | Tests vertical-base logic |
| Both orientations | Ensures maximum is selected |
| Maximum coordinates | Tests overflow handling |
| Multiple points on same y | Widest base should be used |
| Multiple points on same x | Tallest base should be used |

## Edge Cases

### No Shared x or Shared y Coordinates

A common mistake is to assume every set of three points can produce a valid candidate. If every point has a unique `x` and unique `y`, then no horizontal or vertical side can exist. In this situation every group has size one, all base lengths are zero, and the algorithm correctly returns `-1`.

### All Points on a Single Line

Points may share the same horizontal or vertical line, creating a non-zero base. However, if every point lies on that same line, the height is zero and the resulting area is zero. The implementation explicitly requires both base and height to be positive before updating the answer, preventing degenerate triangles from being counted.

### Extremely Large Coordinates

Coordinates may reach `10^6`, producing a maximum doubled area near:

$$(10^6 - 1)^2$$

which is approximately `10^12`. This exceeds 32-bit integer limits. The Go implementation uses `int64`, and Python integers naturally support arbitrary precision, ensuring correct results without overflow.

### Optimal Triangle Does Not Use the First Available Base

There may be many points on the same horizontal or vertical line. Choosing an arbitrary pair can miss the maximum area. The algorithm always uses the extreme endpoints on each line, guaranteeing the largest possible base and therefore the largest possible area obtainable from that line.
assert Solution().maxArea([[1,1],[1,2],[3,2],[3,3]]) == 2  # basic valid case
assert Solution().maxArea([[1,1],[2,2],[3,3]]) == -1      # no axis-parallel side
assert Solution().maxArea([[1,1],[1,2],[1,3]]) == -1      # collinear vertical line, zero area
assert Solution().maxArea([[1,1],[1,2],[2,1]]) == 1       # right triangle
assert Solution().maxArea([[1,1],[1,5],[10,1],[10,5]]) == 36  # rectangle corners
assert Solution().maxArea([[1,1],[2,1],[3,1],[4,1]]) == -1  # all horizontal, zero height effect

Test	Why
rectangle corners	checks maximal horizontal and vertical combinations
no axis-parallel side	ensures -1 is returned
collinear points	verifies degenerate rejection
single valid right triangle	minimal nontrivial valid case
mixed grid	validates correct maximization

Edge Cases

One important edge case occurs when all points lie on distinct x and y coordinates. In this situation, no two points can form a horizontal or vertical base, so the algorithm must correctly return $-1$ without attempting invalid area computations.

Another edge case arises when a valid base exists but all points lie on the same horizontal or vertical line. In this case, although a base length can be computed, the perpendicular height is zero, producing zero area. The implementation explicitly filters this out by requiring the base and height product to be strictly positive before updating the result.

A third edge case involves sparse groups where exactly two points share a coordinate. These are valid bases, but care must be taken to ensure that the grouping logic correctly captures min and max values without requiring more complex combinatorial checks. The hash-map-based extremal storage guarantees correctness even in these minimal configurations.