1311. Largest Magic Square¶

Difficulty: Medium

1311. Largest Magic Square

Medium

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:

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:

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⁶

Solution¶

class Solution {
    private HashSet<Integer> sums;
    public int largestMagicSquare(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int maxi = 1;
        for (int k = n; k >= 2; k--) {
            sums = new HashSet<>();
            if (check(k, grid)) return k;
        }
        return 1;
    }
    private boolean check(int len, int grid[][]) {
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int r1 = i, c1 = j;
                int r2 = r1 + len - 1, c2 = c1 + len - 1;
                if (r2 >= n || c2 >= m) continue;
                check_row(r1, c1, r2, c2, grid); check_col(r1, c1, r2, c2, grid); check_diagonal(r1, c1, r2, c2, grid);
                if (sums.size() == 1) return true;
                sums = new HashSet<>();
            }
        }
        return false;
    }
    private void check_row(int r1, int c1, int r2, int c2, int grid[][]) {
        int n = grid.length, m = grid[0].length;
        for (int i = r1; i <= r2; i++) {
            int sum = 0;
            for (int j = c1; j <= c2; j++) sum += grid[i][j];
            sums.add(sum);
        }
    }
    private void check_col(int r1, int c1, int r2, int c2, int grid[][]) {
        int n = grid.length, m = grid[0].length;
        for (int j = c1; j <= c2; j++) {
            int sum = 0;
            for (int i = r1; i <= r2; i++) sum += grid[i][j];
            sums.add(sum);
        }
    }
    private void check_diagonal(int r1, int c1, int r2, int c2, int grid[][]) {
        int n = grid.length, m = grid[0].length;
        int sum = 0;
        int i = r1, j = c1;
        while (i != r2 && j != c2) {
            sum += grid[i][j];
            i++;
            j++;
        }
        sum += grid[r2][c2];
        sums.add(sum);
        sum = 0;
        i = r1; j = c2;
        while (i != r2 && j != c1) {
            sum += grid[i][j];
            i++;
            j--;
        }
        sum += grid[r2][c1];
        sums.add(sum);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here