Formatted question description: https://leetcode.ca/all/1895.html

1895. Largest Magic Square

Level

Medium

Description

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. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Example 1:

Image text

Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]

Output: 3

Explanation: The largest magic square has a size of 3.

Every row sum, column sum, and diagonal sum of this magic square is equal to 12.

Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
Diagonal sums: 5+4+3 = 6+4+2 = 12

Example 2:

Image text

Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]

Output: 2

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10^6

Solution

The maximum possible size of a magic square is Math.min(m, n). Loop over all side lengths from Math.min(m, n) to 2, and find the largest side length such that there exists at least one magic square with the side length. Once such a side length is found, return the side length. Otherwise, return 1.

class Solution {
    public int largestMagicSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int side = Math.min(m, n); side > 1; side--) {
            if (existMagicSquare(grid, m, n, side))
                return side;
        }
        return 1;
    }

    public boolean existMagicSquare(int[][] grid, int m, int n, int side) {
        int maxRow = m - side, maxColumn = n - side;
        for (int i = 0; i <= maxRow; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                if (isMagicSquare(grid, i, j, side))
                    return true;
            }
        }
        return false;
    }

    public boolean isMagicSquare(int[][] grid, int startRow, int startColumn, int side) {
        Set<Integer> set = new HashSet<Integer>();
        int[] rowSums = new int[side];
        int[] columnSums = new int[side];
        int diagonal1 = 0, diagonal2 = 0;
        for (int i = 0; i < side; i++) {
            for (int j = 0; j < side; j++) {
                rowSums[i] += grid[startRow + i][startColumn + j];
                columnSums[j] += grid[startRow + i][startColumn + j];
                if (i == j)
                    diagonal1 += grid[startRow + i][startColumn + j];
                if (i + j == side - 1)
                    diagonal2 += grid[startRow + i][startColumn + j];
            }
        }
        for (int i = 0; i < side; i++) {
            set.add(rowSums[i]);
            set.add(columnSums[i]);
        }
        set.add(diagonal1);
        set.add(diagonal2);
        return set.size() == 1;
    }
}

############

class Solution {
    private int[][] rowsum;
    private int[][] colsum;

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        rowsum = new int[m + 1][n + 1];
        colsum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1];
                colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1];
            }
        }
        for (int k = Math.min(m, n); k > 1; --k) {
            for (int i = 0; i + k - 1 < m; ++i) {
                for (int j = 0; j + k - 1 < n; ++j) {
                    int i2 = i + k - 1, j2 = j + k - 1;
                    if (check(grid, i, j, i2, j2)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }

    private boolean check(int[][] grid, int x1, int y1, int x2, int y2) {
        int val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1];
        for (int i = x1 + 1; i <= x2; ++i) {
            if (rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val) {
                return false;
            }
        }
        for (int j = y1; j <= y2; ++j) {
            if (colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val) {
                return false;
            }
        }
        int s = 0;
        for (int i = x1, j = y1; i <= x2; ++i, ++j) {
            s += grid[i][j];
        }
        if (s != val) {
            return false;
        }
        s = 0;
        for (int i = x1, j = y2; i <= x2; ++i, --j) {
            s += grid[i][j];
        }
        if (s != val) {
            return false;
        }
        return true;
    }
}

// OJ: https://leetcode.com/problems/largest-magic-square/
// Time: O(MN * min(M, N)^3)
// Space: O(1)
class Solution {
    int M, N;
    bool isMagic(vector<vector<int>>& G, int x, int y, int len) {
        int a = 0, b = 0;
        for (int i = 0; i < len; ++i) {
            a += G[x + i][y + i];
            b += G[x + i][y + len - 1 - i];
        }
        if (a != b) return false;
        for (int i = 0; i < len; ++i) {
            int row = 0, col = 0;
            for (int j = 0; j < len; ++j) {
                row += G[x + i][y + j];
                col += G[x + j][y + i];
            }
            if (row != a || col != a) return false;
        }
        return true;
    }
public:
    int largestMagicSquare(vector<vector<int>>& G) {
        M = G.size(), N = G[0].size();
        for (int i = min(M, N); i >= 2; --i) {
            for (int x = 0; x <= M - i; ++x) {
                for (int y = 0; y <= N - i; ++y) {
                    if (isMagic(G, x, y, i)) return i;
                }
            }
        }
        return 1;
    }
};

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rowsum = [[0] * (n + 1) for _ in range(m + 1)]
        colsum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]
                colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]

        def check(x1, y1, x2, y2):
            val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1]
            for i in range(x1 + 1, x2 + 1):
                if rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val:
                    return False
            for j in range(y1, y2 + 1):
                if colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val:
                    return False
            s, i, j = 0, x1, y1
            while i <= x2:
                s += grid[i][j]
                i += 1
                j += 1
            if s != val:
                return False
            s, i, j = 0, x1, y2
            while i <= x2:
                s += grid[i][j]
                i += 1
                j -= 1
            if s != val:
                return False
            return True

        for k in range(min(m, n), 1, -1):
            i = 0
            while i + k - 1 < m:
                j = 0
                while j + k - 1 < n:
                    i2, j2 = i + k - 1, j + k - 1
                    if check(i, j, i2, j2):
                        return k
                    j += 1
                i += 1
        return 1

############

# 1895. Largest Magic Square
# https://leetcode.com/problems/largest-magic-square

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        self.res = 1
        
        rowPrefix = [[i for i in row] for row in grid]
        colPrefix = [[i for i in row] for row in grid]
        dlPrefix = [[i for i in row] for row in grid]
        drPrefix = [[i for i in row] for row in grid]
        
        # row
        for i in range(rows):
            for j in range(cols - 1):
                rowPrefix[i][j + 1] += rowPrefix[i][j]

        # cols
        for i in range(rows - 1):
            for j in range(cols):
                colPrefix[i + 1][j] += colPrefix[i][j]

        # diag left
        for i in range(rows - 1):
            for j in range(cols - 1):
                dlPrefix[i + 1][j + 1] += dlPrefix[i][j]

        # diag right
        for i in range(rows - 1):
            for j in range(cols - 1, 0, -1):
                drPrefix[i + 1][j - 1] += drPrefix[i][j]

        def dfs(x, y, size):
            
            if x + size < rows and y + size < cols:
                rowSum = [rowPrefix[i][y + size] - (0 if y == 0 else rowPrefix[i][y - 1]) for i in range(x, x + size + 1)]
                colSum = [colPrefix[x + size][j] - (0 if x == 0 else colPrefix[x - 1][j]) for j in range(y, y + size + 1)]
                diagLeft = dlPrefix[x + size][y + size] - (0 if x == 0 or y == 0 else dlPrefix[x - 1][y - 1])
                diagRight = drPrefix[x + size][y] - (0 if x - 1 < 0 or y + size + 1 >= cols else drPrefix[x - 1][y + size + 1])
                
                if (all(r == rowSum[0] for r in rowSum) and all(c == colSum[0] for c in colSum) and rowSum[0] == colSum[0] == diagLeft == diagRight):
                    self.res = max(self.res, size + 1)
                    
                dfs(x, y, size + 1)
            
        for i in range(rows):
            for j in range(cols):
                dfs(i, j, 1)
        
        return self.res

func largestMagicSquare(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	rowsum := make([][]int, m+1)
	colsum := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		rowsum[i] = make([]int, n+1)
		colsum[i] = make([]int, n+1)
	}
	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			rowsum[i][j] = rowsum[i][j-1] + grid[i-1][j-1]
			colsum[i][j] = colsum[i-1][j] + grid[i-1][j-1]
		}
	}
	for k := min(m, n); k > 1; k-- {
		for i := 0; i+k-1 < m; i++ {
			for j := 0; j+k-1 < n; j++ {
				i2, j2 := i+k-1, j+k-1
				if check(grid, rowsum, colsum, i, j, i2, j2) {
					return k
				}
			}
		}
	}
	return 1
}

func check(grid, rowsum, colsum [][]int, x1, y1, x2, y2 int) bool {
	val := rowsum[x1+1][y2+1] - rowsum[x1+1][y1]
	for i := x1 + 1; i < x2+1; i++ {
		if rowsum[i+1][y2+1]-rowsum[i+1][y1] != val {
			return false
		}
	}
	for j := y1; j < y2+1; j++ {
		if colsum[x2+1][j+1]-colsum[x1][j+1] != val {
			return false
		}
	}
	s := 0
	for i, j := x1, y1; i <= x2; i, j = i+1, j+1 {
		s += grid[i][j]
	}
	if s != val {
		return false
	}
	s = 0
	for i, j := x1, y2; i <= x2; i, j = i+1, j-1 {
		s += grid[i][j]
	}
	if s != val {
		return false
	}
	return true
}

func min(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function largestMagicSquare(grid: number[][]): number {
    let m = grid.length,
        n = grid[0].length;
    // 前缀和
    let rowSum = Array.from({ length: m + 1 }, (v, i) =>
            new Array(n + 1).fill(0),
        ),
        colSum = Array.from({ length: m + 1 }, v => new Array(n + 1).fill(0));
    for (let i = 0; i < m; i++) {
        rowSum[i + 1][1] = grid[i][0];
        for (let j = 1; j < n; j++) {
            rowSum[i + 1][j + 1] = rowSum[i + 1][j] + grid[i][j];
        }
    }

    for (let j = 0; j < n; j++) {
        colSum[1][j + 1] = grid[0][j];
        for (let i = 1; i < m; i++) {
            colSum[i + 1][j + 1] = colSum[i][j + 1] + grid[i][j];
        }
    }
    // console.log(rowSum, colSum)
    // 寻找最大k
    for (let k = Math.min(m, n); k > 1; k--) {
        for (let i = 0; i + k - 1 < m; i++) {
            for (let j = 0; j + k - 1 < n; j++) {
                let x2 = i + k - 1,
                    y2 = j + k - 1;
                if (valid(grid, rowSum, colSum, i, j, x2, y2)) {
                    return k;
                }
            }
        }
    }
    return 1;
}

function valid(
    grid: number[][],
    rowSum: number[][],
    colSum: number[][],
    x1: number,
    y1: number,
    x2: number,
    y2: number,
): boolean {
    let diff = rowSum[x1 + 1][y2 + 1] - rowSum[x1 + 1][y1];
    // 行
    for (let i = x1 + 1; i <= x2; i++) {
        if (diff != rowSum[i + 1][y2 + 1] - rowSum[i + 1][y1]) {
            return false;
        }
    }
    // 列
    for (let j = y1; j <= y2; j++) {
        if (diff != colSum[x2 + 1][j + 1] - colSum[x1][j + 1]) {
            return false;
        }
    }
    // 主队对角线
    let mainSum = diff;
    for (let i = x1, j = y1; i <= x2; i++, j++) {
        mainSum -= grid[i][j];
    }
    if (mainSum != 0) return false;
    // 副对角线
    let subSum = diff;
    for (let i = x1, j = y2; i <= x2; i++, j--) {
        subSum -= grid[i][j];
    }
    if (subSum != 0) return false;
    return true;
}

1895 - Largest Magic Square

1895. Largest Magic Square

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1895. Largest Magic Square

Level

Description

Solution

All Problems

All Solutions