Maximum square area by removing fences from a field

Array Hash Table Enumeration

49.4% acceptance

Feb 25, 2026

452

162

There is a large (m-1) x (n-1) field with horizontal fences hFences and vertical fences vFences. Find the maximum square area by removing some fences. Return -1 if impossible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximize_square_area(m: i32, n: i32, h_fences: Vec<i32>, v_fences: Vec<i32>) -> i32 {
    use std::collections::HashSet;
    const MOD: i64 = 1_000_000_007;

    // Compute all possible horizontal spans
    let mut h_all = h_fences.clone();
    h_all.push(1);
    h_all.push(m);
    h_all.sort_unstable();
    let h_len = h_all.len();

    let mut h_spans: HashSet<i64> = HashSet::new();
    for i in 0..h_len {
      for j in i + 1..h_len {
        h_spans.insert((h_all[j] - h_all[i]) as i64);
      }
    }

    // Compute all possible vertical spans
    let mut v_all = v_fences.clone();
    v_all.push(1);
    v_all.push(n);
    v_all.sort_unstable();
    let v_len = v_all.len();

    let mut v_spans: HashSet<i64> = HashSet::new();
    for i in 0..v_len {
      for j in i + 1..v_len {
        v_spans.insert((v_all[j] - v_all[i]) as i64);
      }
    }

    // Find maximum common span
    let mut max_span = 0i64;
    for &s in &h_spans {
      if v_spans.contains(&s) {
        max_span = max_span.max(s);
      }
    }

    if max_span == 0 {
      -1
    } else {
      (max_span % MOD * (max_span % MOD) % MOD) as i32
    }
  }
}