Tiling a rectangle with the fewest squares

Backtracking

54.8% acceptance

Feb 25, 2026

721

582

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn tiling_rectangle(n: i32, m: i32) -> i32 {
    // Special case for hard problem
    if n == m { return 1; }
    let (n, m) = (n as usize, m as usize);
    let mut ans = n * m; // worst case: all 1x1
    let mut height = vec![0usize; m];
    Self::backtrack(&mut height, n, m, 0, &mut ans);
    ans as i32
  }

  fn backtrack(height: &mut Vec<usize>, n: usize, m: usize, count: usize, ans: &mut usize) {
    if count >= *ans { return; }

    // Find the position with minimum height
    let min_h = *height.iter().min().unwrap();
    if min_h == n { *ans = (*ans).min(count); return; }

    // Find leftmost column with min height
    let left = height.iter().position(|&h| h == min_h).unwrap();

    // Find rightmost contiguous column with min height
    let mut right = left;
    while right + 1 < m && height[right + 1] == min_h {
      right += 1;
    }

    // Try all square sizes from max possible down to 1
    let max_size = (right - left + 1).min(n - min_h);
    for size in (1..=max_size).rev() {
      for j in left..left + size {
        height[j] += size;
      }
      Self::backtrack(height, n, m, count + 1, ans);
      for j in left..left + size {
        height[j] -= size;
      }
    }
  }
}