Problem Description

You are given a 2D grid of integers, represented as grid. Your task is to count the number of 3x3 "magic square" subgrids within grid.
A 3x3 magic square is a 3x3 grid containing all the numbers from 1 to 9 exactly once, such that each row, each column, and both main diagonals all sum to the same value (which, for 1-9, is always 15).

• Input: grid is an m x n matrix of integers where m >= 3 and n >= 3.
• Output: Return the total number of 3x3 magic square subgrids in grid.
• Constraints:
  • Each magic square must use every integer from 1 to 9 exactly once.
  • Each row, column, and both diagonals must sum to 15.
  • Subgrids may overlap.

Thought Process

At first glance, the problem appears to require checking every possible 3x3 subgrid in the input grid to see if it forms a magic square. Since the grid can be up to 10x10, brute-forcing is feasible.

• The naive approach is to extract every 3x3 subgrid and check if it satisfies the magic square conditions.
• For each subgrid, we need to ensure:
  • All numbers are unique and in the range 1-9.
  • The sum of every row, column, and the two diagonals is 15.
• Optimization comes from realizing that only 3x3 grids with 5 at the center can be magic squares (because 5 is always the center in a 3x3 1-9 magic square).
• We can skip checking subgrids where the center is not 5, reducing the number of checks.

Solution Approach

• Step 1: Iterate over every possible 3x3 subgrid within grid. For an m x n grid, the top-left corner of each subgrid can be at positions (i, j) where i ranges from 0 to m-3 and j from 0 to n-3.
• Step 2: For each 3x3 subgrid:
  • Check if the center cell is 5. If not, skip this subgrid (optimization).
  • Collect all 9 numbers in the subgrid. Check if they are all unique and in the range 1-9.
  • Calculate the sum of each row, each column, and both diagonals. All must be 15.
• Step 3: If all conditions are met, increment the magic square counter.
• Step 4: Return the total count after checking all subgrids.

We use sets to check for uniqueness and range, and simple loops to check row, column, and diagonal sums.

Example Walkthrough

Consider the following input grid:

  4 3 8 4
  9 5 1 9
  2 7 6 2
  

• The only 3x3 subgrid starting at (0,0) is:

        4 3 8
        9 5 1
        2 7 6
        

  - Center is 5 (good). - All numbers are unique and between 1 and 9. - Rows: 4+3+8=15, 9+5+1=15, 2+7+6=15. - Columns: 4+9+2=15, 3+5+7=15, 8+1+6=15. - Diagonals: 4+5+6=15, 8+5+2=15.
  This is a magic square, so count = 1.
• Next subgrid starting at (0,1):

        3 8 4
        5 1 9
        7 6 2
        

  - Center is 1 (not 5), so skip.

After checking all possible subgrids, the answer is 1.

Code Implementation

class Solution:
    def numMagicSquaresInside(self, grid):
        def is_magic(i, j):
            nums = [grid[x][y] for x in range(i, i+3) for y in range(j, j+3)]
            if sorted(nums) != list(range(1, 10)):
                return False
            rows = [sum(grid[i+k][j:j+3]) for k in range(3)]
            cols = [sum(grid[i+x][j+k] for x in range(3)) for k in range(3)]
            diag1 = grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2]
            diag2 = grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j]
            return all(s == 15 for s in rows+cols+[diag1, diag2])
        
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m-2):
            for j in range(n-2):
                if grid[i+1][j+1] != 5:
                    continue
                if is_magic(i, j):
                    count += 1
        return count
      

class Solution {
public:
    bool isMagic(vector<vector<int>>& grid, int x, int y) {
        vector<int> nums;
        for (int i = x; i < x+3; ++i)
            for (int j = y; j < y+3; ++j)
                nums.push_back(grid[i][j]);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < 9; ++i)
            if (nums[i] != i+1) return false;
        for (int i = 0; i < 3; ++i) {
            if (grid[x+i][y] + grid[x+i][y+1] + grid[x+i][y+2] != 15) return false;
            if (grid[x][y+i] + grid[x+1][y+i] + grid[x+2][y+i] != 15) return false;
        }
        if (grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2] != 15) return false;
        if (grid[x][y+2] + grid[x+1][y+1] + grid[x+2][y] != 15) return false;
        return true;
    }
    int numMagicSquaresInside(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), count = 0;
        for (int i = 0; i <= m-3; ++i) {
            for (int j = 0; j <= n-3; ++j) {
                if (grid[i+1][j+1] != 5) continue;
                if (isMagic(grid, i, j)) ++count;
            }
        }
        return count;
    }
};
      

class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        for (int i = 0; i <= m-3; ++i) {
            for (int j = 0; j <= n-3; ++j) {
                if (grid[i+1][j+1] != 5) continue;
                if (isMagic(grid, i, j)) count++;
            }
        }
        return count;
    }
    private boolean isMagic(int[][] grid, int x, int y) {
        int[] nums = new int[9];
        int idx = 0;
        for (int i = x; i < x+3; ++i)
            for (int j = y; j < y+3; ++j)
                nums[idx++] = grid[i][j];
        Arrays.sort(nums);
        for (int i = 0; i < 9; ++i)
            if (nums[i] != i+1) return false;
        for (int i = 0; i < 3; ++i) {
            if (grid[x+i][y] + grid[x+i][y+1] + grid[x+i][y+2] != 15) return false;
            if (grid[x][y+i] + grid[x+1][y+i] + grid[x+2][y+i] != 15) return false;
        }
        if (grid[x][y] + grid[x+1][y+1] + grid[x+2][y+2] != 15) return false;
        if (grid[x][y+2] + grid[x+1][y+1] + grid[x+2][y] != 15) return false;
        return true;
    }
}
      

var numMagicSquaresInside = function(grid) {
    function isMagic(i, j) {
        let nums = [];
        for (let x = i; x < i+3; x++)
            for (let y = j; y < j+3; y++)
                nums.push(grid[x][y]);
        nums.sort((a, b) => a-b);
        for (let k = 0; k < 9; k++)
            if (nums[k] !== k+1) return false;
        for (let k = 0; k < 3; k++) {
            if (grid[i+k][j] + grid[i+k][j+1] + grid[i+k][j+2] !== 15) return false;
            if (grid[i][j+k] + grid[i+1][j+k] + grid[i+2][j+k] !== 15) return false;
        }
        if (grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] !== 15) return false;
        if (grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] !== 15) return false;
        return true;
    }
    let m = grid.length, n = grid[0].length, count = 0;
    for (let i = 0; i <= m-3; i++) {
        for (let j = 0; j <= n-3; j++) {
            if (grid[i+1][j+1] !== 5) continue;
            if (isMagic(i, j)) count++;
        }
    }
    return count;
};
      

Time and Space Complexity

• Brute-force approach:
  • There are (m-2) x (n-2) possible 3x3 subgrids.
  • For each subgrid, checking all conditions takes O(1) time (since subgrid size is fixed).
  • Total Time Complexity: O(mn)
  • Space Complexity: O(1), ignoring input and using only a few local variables.
• With center-5 optimization:
  • We skip many subgrids early, but worst-case time is still O(mn).

Summary

This problem is a classic application of brute-force search with a simple optimization: only checking subgrids whose center is 5. By systematically iterating over all possible 3x3 subgrids and verifying the magic square properties, we ensure correctness while keeping the solution efficient for the given constraints. The approach leverages the mathematical structure of 3x3 magic squares (unique numbers 1-9, sum 15 per row/col/diagonal), leading to a clean, readable, and robust solution.