Maximize area of square hole in grid

Array Sorting

61.9% acceptance

Feb 25, 2026

637

278

You are given the two integers, n and m and two integer arrays, hBars and vBars. The grid has n + 2 horizontal and m + 2 vertical bars, creating 1 x 1 unit cells. The bars are indexed starting from 1. You can remove some of the bars in hBars from horizontal bars and some of the bars in vBars from vertical bars. Note that other bars are fixed and cannot be removed. Return an integer denoting the maximum area of a square-shaped hole in the grid, after removing some bars (possibly none).

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximize_square_hole_area(_n: i32, _m: i32, h_bars: Vec<i32>, v_bars: Vec<i32>) -> i32 {
    fn max_consecutive(mut bars: Vec<i32>) -> i32 {
      bars.sort_unstable();
      let mut max_run = 1i32;
      let mut run = 1i32;
      for i in 1..bars.len() {
        if bars[i] == bars[i - 1] + 1 {
          run += 1;
          max_run = max_run.max(run);
        } else {
          run = 1;
        }
      }
      max_run + 1 // +1 for the outer fixed bars
    }
    let h = max_consecutive(h_bars);
    let v = max_consecutive(v_bars);
    let side = h.min(v);
    side * side
  }
}