Largest magic square

Array Matrix Prefix Sum

75.3% acceptance

Feb 25, 2026

609

332

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. Every 1 x 1 grid is trivially a magic square. Given an m x n integer grid, return the size (side length k) of the largest magic square that can be found within this grid.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn largest_magic_square(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    // Prefix sums for rows and columns
    let mut row_prefix = vec![vec![0i64; n + 1]; m];
    let mut col_prefix = vec![vec![0i64; m + 1]; n];

    for i in 0..m {
      for j in 0..n {
        row_prefix[i][j + 1] = row_prefix[i][j] + grid[i][j] as i64;
      }
    }
    for j in 0..n {
      for i in 0..m {
        col_prefix[j][i + 1] = col_prefix[j][i] + grid[i][j] as i64;
      }
    }

    let row_sum = |r: usize, c1: usize, c2: usize| -> i64 {
      row_prefix[r][c2 + 1] - row_prefix[r][c1]
    };
    let col_sum = |c: usize, r1: usize, r2: usize| -> i64 {
      col_prefix[c][r2 + 1] - col_prefix[c][r1]
    };

    let max_k = m.min(n);
    let mut ans = 1;

    for k in (2..=max_k).rev() {
      let mut found = false;
      'outer: for r in 0..=m - k {
        for c in 0..=n - k {
          let target = row_sum(r, c, c + k - 1);
          // Check all rows
          let rows_ok = (r..r + k).all(|i| row_sum(i, c, c + k - 1) == target);
          if !rows_ok { continue; }
          // Check all columns
          let cols_ok = (c..c + k).all(|j| col_sum(j, r, r + k - 1) == target);
          if !cols_ok { continue; }
          // Check main diagonal
          let diag1: i64 = (0..k).map(|d| grid[r + d][c + d] as i64).sum();
          if diag1 != target { continue; }
          // Check anti-diagonal
          let diag2: i64 = (0..k).map(|d| grid[r + d][c + k - 1 - d] as i64).sum();
          if diag2 != target { continue; }
          ans = k;
          found = true;
          break 'outer;
        }
      }
      if found { break; }
    }
    ans as i32
  }
}