Find maximum area of a triangle

Array Hash Table Math Greedy Geometry Enumeration

29.1% acceptance

Feb 25, 2026

You are given a 2D array coords of size n x 2, representing the coordinates of n points. Find twice the maximum area of a triangle with its corners at any three elements from coords, such that at least one side of this triangle is parallel to x-axis or y-axis. If no such triangle exists, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_area(coords: Vec<Vec<i32>>) -> i64 {
    // At least one side parallel to x-axis: two points share same y-coordinate.
    // Area = (1/2) * base * height. base = |x2-x1|, height = |y3-y_shared|.
    // 2*Area = base * height.
    // Maximize: for each y-value, maximize base (max_x - min_x for that y),
    //           then use the point with max or min y from another row as height.
    // Similarly for sides parallel to y-axis.

    use std::collections::HashMap;
    let mut x_groups: HashMap<i32, (i32, i32)> = HashMap::new(); // x -> (min_y, max_y)
    let mut y_groups: HashMap<i32, (i32, i32)> = HashMap::new(); // y -> (min_x, max_x)

    let mut global_min_x = i32::MAX;
    let mut global_max_x = i32::MIN;
    let mut global_min_y = i32::MAX;
    let mut global_max_y = i32::MIN;

    for c in &coords {
      let (x, y) = (c[0], c[1]);
      let xe = x_groups.entry(x).or_insert((i32::MAX, i32::MIN));
      xe.0 = xe.0.min(y);
      xe.1 = xe.1.max(y);
      let ye = y_groups.entry(y).or_insert((i32::MAX, i32::MIN));
      ye.0 = ye.0.min(x);
      ye.1 = ye.1.max(x);
      global_min_x = global_min_x.min(x);
      global_max_x = global_max_x.max(x);
      global_min_y = global_min_y.min(y);
      global_max_y = global_max_y.max(y);
    }

    let mut ans = -1i64;

    // Horizontal base (side parallel to x-axis): two points share same y
    // base = max_x[y] - min_x[y], height = |y3 - y| maximized by global min/max y
    for (&y, &(min_x, max_x)) in &y_groups {
      if min_x == max_x { continue; } // need at least 2 distinct x
      let base = (max_x - min_x) as i64;
      // Third point: any y' != y (but can be any x). Use global extremes.
      let h1 = (y - global_min_y).abs() as i64;
      let h2 = (y - global_max_y).abs() as i64;
      let h = h1.max(h2);
      if h > 0 {
        ans = ans.max(base * h);
      }
    }

    // Vertical base (side parallel to y-axis): two points share same x
    // base = max_y[x] - min_y[x], height = |x3 - x| maximized by global min/max x
    for (&x, &(min_y, max_y)) in &x_groups {
      if min_y == max_y { continue; }
      let base = (max_y - min_y) as i64;
      let h1 = (x - global_min_x).abs() as i64;
      let h2 = (x - global_max_x).abs() as i64;
      let h = h1.max(h2);
      if h > 0 {
        ans = ans.max(base * h);
      }
    }

    ans
  }
}