1895. Largest Magic Square

/**
 * Problem: LeetCode 1895 - Largest Magic Square
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // rowSum[r][c + 1] stores the prefix sum of row r up to index c
        int[][] rowSum = new int[m][n + 1];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                rowSum[r][c + 1] = rowSum[r][c] + grid[r][c];
            }
        }

        // colSum[r + 1][c] stores the prefix sum of column c up to index r
        int[][] colSum = new int[m + 1][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                colSum[r + 1][c] = colSum[r][c] + grid[r][c];
            }
        }

        // Test square sizes from largest possible min(m, n) down to 2
        for (int k = Math.min(m, n); k >= 2; k--) {
            for (int r = 0; r <= m - k; r++) {
                for (int c = 0; c <= n - k; c++) {
                    if (isMagic(grid, rowSum, colSum, r, c, k)) {
                        return k;
                    }
                }
            }
        }

        return 1;
    }

    private boolean isMagic(int[][] grid, int[][] rowSum, int[][] colSum, int r, int c, int k) {
        int target = rowSum[r][c + k] - rowSum[r][c];

        // Check remaining row sums
        for (int i = 1; i < k; i++) {
            if (rowSum[r + i][c + k] - rowSum[r + i][c] != target) {
                return false;
            }
        }

        // Check all column sums
        for (int j = 0; j < k; j++) {
            if (colSum[r + k][c + j] - colSum[r][c + j] != target) {
                return false;
            }
        }

        // Check main diagonal sum
        int d1 = 0;
        for (int i = 0; i < k; i++) {
            d1 += grid[r + i][c + i];
        }
        if (d1 != target) {
            return false;
        }

        // Check anti-diagonal sum
        int d2 = 0;
        for (int i = 0; i < k; i++) {
            d2 += grid[r + i][c + k - 1 - i];
        }
        if (d2 != target) {
            return false;
        }

        return true;
    }
}

"""
Problem: LeetCode 1895 - Largest Magic Square
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:

    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        # Prefix sums for rows
        row_sum = [[0] * (n + 1) for _ in range(m)]
        for r in range(m):
            for c in range(n):
                row_sum[r][c + 1] = row_sum[r][c] + grid[r][c]

        # Prefix sums for columns
        col_sum = [[0] * n for _ in range(m + 1)]
        for r in range(m):
            for c in range(n):
                col_sum[r + 1][c] = col_sum[r][c] + grid[r][c]

        def is_magic(r: int, c: int, k: int) -> bool:
            target = row_sum[r][c + k] - row_sum[r][c]

            # Check rows
            for i in range(1, k):
                if row_sum[r + i][c + k] - row_sum[r + i][c] != target:
                    return False

            # Check columns
            for j in range(k):
                if col_sum[r + k][c + j] - col_sum[r][c + j] != target:
                    return False

            # Check main diagonal
            d1 = sum(grid[r + i][c + i] for i in range(k))
            if d1 != target:
                return False

            # Check anti-diagonal
            d2 = sum(grid[r + i][c + k - 1 - i] for i in range(k))
            if d2 != target:
                return False

            return True

        for k in range(min(m, n), 1, -1):
            for r in range(m - k + 1):
                for c in range(n - k + 1):
                    if is_magic(r, c, k):
                        return k

        return 1

/**
 * Problem: LeetCode 1895 - Largest Magic Square
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // Row prefix sums
        vector<vector<int>> rowSum(m, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                rowSum[r][c + 1] = rowSum[r][c] + grid[r][c];
            }
        }

        // Col prefix sums
        vector<vector<int>> colSum(m + 1, vector<int>(n, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                colSum[r + 1][c] = colSum[r][c] + grid[r][c];
            }
        }

        auto isMagic = [&](int r, int c, int k) -> bool {
            int target = rowSum[r][c + k] - rowSum[r][c];

            // Check remaining rows
            for (int i = 1; i < k; i++) {
                if (rowSum[r + i][c + k] - rowSum[r + i][c] != target) {
                    return false;
                }
            }

            // Check all columns
            for (int j = 0; j < k; j++) {
                if (colSum[r + k][c + j] - colSum[r][c + j] != target) {
                    return false;
                }
            }

            // Check main diagonal
            int d1 = 0;
            for (int i = 0; i < k; i++) {
                d1 += grid[r + i][c + i];
            }
            if (d1 != target) return false;

            // Check anti-diagonal
            int d2 = 0;
            for (int i = 0; i < k; i++) {
                d2 += grid[r + i][c + k - 1 - i];
            }
            if (d2 != target) return false;

            return true;
        };

        for (int k = min(m, n); k >= 2; k--) {
            for (int r = 0; r <= m - k; r++) {
                for (int c = 0; c <= n - k; c++) {
                    if (isMagic(r, c, k)) {
                        return k;
                    }
                }
            }
        }

        return 1;
    }
};

/**
 * Problem: LeetCode 1895 - Largest Magic Square
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestMagicSquare = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    // Row prefix sums
    const rowSum = Array.from({ length: m }, () => new Int32Array(n + 1));
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            rowSum[r][c + 1] = rowSum[r][c] + grid[r][c];
        }
    }

    // Col prefix sums
    const colSum = Array.from({ length: m + 1 }, () => new Int32Array(n));
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            colSum[r + 1][c] = colSum[r][c] + grid[r][c];
        }
    }

    function isMagic(r, c, k) {
        const target = rowSum[r][c + k] - rowSum[r][c];

        // Check rows
        for (let i = 1; i < k; i++) {
            if (rowSum[r + i][c + k] - rowSum[r + i][c] !== target) return false;
        }

        // Check columns
        for (let j = 0; j < k; j++) {
            if (colSum[r + k][c + j] - colSum[r][c + j] !== target) return false;
        }

        // Check main diagonal
        let d1 = 0;
        for (let i = 0; i < k; i++) {
            d1 += grid[r + i][c + i];
        }
        if (d1 !== target) return false;

        // Check anti-diagonal
        let d2 = 0;
        for (let i = 0; i < k; i++) {
            d2 += grid[r + i][c + k - 1 - i];
        }
        if (d2 !== target) return false;

        return true;
    }

    for (let k = Math.min(m, n); k >= 2; k--) {
        for (let r = 0; r <= m - k; r++) {
            for (let c = 0; c <= n - k; c++) {
                if (isMagic(r, c, k)) {
                    return k;
                }
            }
        }
    }

    return 1;
};