Magic Squares In Grid

Med

#0794Time: O(R * C), where R is the number of rows and C is the number of columns. We iterate through approximately R * C subgrids, and the check for each is a constant time operation (O(1) since it's always 3x3).Space: O(1). The extra space used is a constant-size array for checking distinctness, which does not depend on the input grid size.

Patterns

Math

Data structures

Array Hash Table Matrix

Prompt

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given a row x col grid of integers, how many 3 x 3 magic square subgrids are there?

Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.

Example 1:

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2:

Input: grid = [[8]]
Output: 0

Constraints:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every possible 3x3 subgrid in the input grid. For each subgrid, it performs a comprehensive check to see if it satisfies all the properties of a magic square.

Algorithm

Initialize a counter magic_squares_count to 0.
If the grid dimensions are smaller than 3x3, return 0.
Iterate through each row r from 0 to grid.length - 3.
Inside this loop, iterate through each column c from 0 to grid[0].length - 3.
For the 3x3 subgrid starting at (r, c), call a helper function isMagic.
The isMagic helper function performs the following checks:
- Verify that all 9 elements are distinct numbers from 1 to 9. A frequency array can be used for this.
- Calculate the sum of each of the 3 rows, 3 columns, and 2 diagonals.
- Return true if all 8 sums are equal to 15, otherwise return false.
If isMagic returns true, increment magic_squares_count.
After the loops complete, return magic_squares_count.

Walkthrough

The algorithm iterates through the main grid with nested loops, considering each cell (r, c) as a potential top-left corner of a 3x3 subgrid. This is possible for r from 0 to rows-3 and c from 0 to cols-3.

A helper function, isMagic(grid, r, c), is called for each subgrid. This function validates two main properties:

Distinct Numbers from 1 to 9: It checks if all 9 numbers in the subgrid are unique and fall within the required range of 1 to 9. This can be done using a frequency array or a set. If any number is out of range or duplicated, the subgrid is not magic.
Constant Sum: It verifies that the sum of numbers in each of the three rows, three columns, and both main diagonals is equal to the magic constant, which is 15 for numbers 1-9.

A counter is maintained and incremented for every subgrid that passes all these checks.

1class Solution {2    public int numMagicSquaresInside(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        if (rows < 3 || cols < 3) {6            return 0;7        }8        int count = 0;9        for (int r = 0; r <= rows - 3; r++) {10            for (int c = 0; c <= cols - 3; c++) {11                if (isMagic(grid, r, c)) {12                    count++;13                }14            }15        }16        return count;17    }18 19    private boolean isMagic(int[][] grid, int r, int c) {20        // 1. Check for distinct numbers 1-921        int[] seen = new int[16];22        for (int i = 0; i < 3; i++) {23            for (int j = 0; j < 3; j++) {24                int val = grid[r + i][c + j];25                if (val < 1 || val > 9 || seen[val] > 0) {26                    return false;27                }28                seen[val]++;29            }30        }31 32        // 2. Check sums33        int row1 = grid[r][c] + grid[r][c+1] + grid[r][c+2];34        int row2 = grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2];35        int row3 = grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2];36        int col1 = grid[r][c] + grid[r+1][c] + grid[r+2][c];37        int col2 = grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1];38        int col3 = grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2];39        int diag1 = grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2];40        int diag2 = grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c];41 42        return row1 == 15 && row2 == 15 && row3 == 15 &&43               col1 == 15 && col2 == 15 && col3 == 15 &&44               diag1 == 15 && diag2 == 15;45    }46}

Complexity

Time

O(R * C), where R is the number of rows and C is the number of columns. We iterate through approximately R * C subgrids, and the check for each is a constant time operation (O(1) since it's always 3x3).

Space

O(1). The extra space used is a constant-size array for checking distinctness, which does not depend on the input grid size.

Trade-offs

Pros

Simple and direct implementation of the problem definition.
Easy to understand and verify its correctness.

Cons

Inefficient as it performs a full, expensive check on every single 3x3 subgrid.
It doesn't leverage any specific properties of magic squares for optimization.

This approach significantly optimizes the brute-force method by first applying a quick filter. A fundamental property of a 3x3 magic square (using numbers 1-9) is that its center element must always be 5. By checking this condition first, we can avoid the expensive full validation for a majority of subgrids.

Algorithm

Initialize magic_squares_count to 0.
If the grid dimensions are smaller than 3x3, return 0.
Iterate through each row r from 0 to grid.length - 3.
Inside this loop, iterate through each column c from 0 to grid[0].length - 3.
Optimization: Check if the center element of the subgrid, grid[r+1][c+1], is 5.
If it is not 5, continue to the next iteration, skipping the current subgrid.
If the center is 5, call the isMagic helper function to perform the full validation (check distinct numbers 1-9 and all 8 sums are 15).
If isMagic returns true, increment magic_squares_count.
After the loops complete, return magic_squares_count.

Walkthrough

The algorithm iterates through all potential 3x3 subgrids, just like the brute-force approach. However, for each subgrid, before performing the full validation, it checks if the center element grid[r+1][c+1] is equal to 5.

If the center element is not 5, the subgrid cannot be a magic square, and the algorithm immediately moves to the next subgrid, skipping the costly checks. Only if the center element is 5 does the algorithm proceed to the full validation. This pre-check drastically reduces the number of full validations needed, leading to a much faster average-case runtime.

1class Solution {2    public int numMagicSquaresInside(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        if (rows < 3 || cols < 3) {6            return 0;7        }8        int count = 0;9        for (int r = 0; r <= rows - 3; r++) {10            for (int c = 0; c <= cols - 3; c++) {11                // Optimization: center must be 512                if (grid[r + 1][c + 1] == 5) {13                    if (isMagic(grid, r, c)) {14                        count++;15                    }16                }17            }18        }19        return count;20    }21 22    private boolean isMagic(int[][] grid, int r, int c) {23        // A more compact way to check distinctness and sums.24        // We already know the center is 5.25        int[] seen = new int[10];26        for (int i = 0; i < 3; i++) {27            for (int j = 0; j < 3; j++) {28                int val = grid[r + i][c + j];29                if (val < 1 || val > 9 || seen[val] > 0) return false;30                seen[val] = 1;31            }32        }33 34        if (grid[r][c] + grid[r][c+1] + grid[r][c+2] != 15) return false;35        if (grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2] != 15) return false;36        if (grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2] != 15) return false;37        if (grid[r][c] + grid[r+1][c] + grid[r+2][c] != 15) return false;38        if (grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1] != 15) return false;39        if (grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2] != 15) return false;40        if (grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2] != 15) return false;41        if (grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c] != 15) return false;42        43        return true;44    }45}

Complexity

Time

O(R * C). The worst-case complexity remains the same, but the average-case performance is much better because the expensive `isMagic` function is called only when the center element is 5.

Space

O(1). The space usage is constant as it does not depend on the input size.

Trade-offs

Pros

Much more efficient on average than the naive brute-force approach.
Simple yet powerful optimization based on a key mathematical property.

Cons

The worst-case time complexity is technically the same as the unoptimized version (e.g., for a grid filled with 5s).

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] grid;8public9  int numMagicSquaresInside(int[][] grid) {10    m = grid.length;11    n = grid[0].length;12    this.grid = grid;13    int ans = 0;14    for (int i = 0; i < m; ++i) {15      for (int j = 0; j < n; ++j) {16        ans += check(i, j);17      }18    }19    return ans;20  }21private22  int check(int i, int j) {23    if (i + 3 > m || j + 3 > n) {24      return 0;25    }26    int[] cnt = new int[16];27    int[] row = new int[3];28    int[] col = new int[3];29    int a = 0, b = 0;30    for (int x = i; x < i + 3; ++x) {31      for (int y = j; y < j + 3; ++y) {32        int v = grid[x][y];33        if (v < 1 || v > 9 || ++cnt[v] > 1) {34          return 0;35        }36        row[x - i] += v;37        col[y - j] += v;38        if (x - i == y - j) {39          a += v;40        }41        if (x - i + y - j == 2) {42          b += v;43        }44      }45    }46    if (a != b) {47      return 0;48    }49    for (int k = 0; k < 3; ++k) {50      if (row[k] != a || col[k] != a) {51        return 0;52      }53    }54    return 1;55  }56}

1function numMagicSquaresInside ( grid ) { const m = grid . length ; const n = grid [ 0 ]. length ; const check = ( i , j ) => { if ( i + 3 > m || j + 3 > n ) { return 0 ; } const cnt = Array ( 16 ). fill ( 0 ); const row = Array ( 3 ). fill ( 0 ); const col = Array ( 3 ). fill ( 0 ); let [ a , b ] = [ 0 , 0 ]; for ( let x = i ; x < i + 3 ; ++ x ) { for ( let y = j ; y < j + 3 ; ++ y ) { const v = grid [ x ][ y ]; if ( v < 1 || v > 9 || ++ cnt [ v ] > 1 ) { return 0 ; } row [ x - i ] += v ; col [ y - j ] += v ; if ( x - i === y - j ) { a += v ; } if ( x - i === 2 - ( y - j )) { b += v ; } } } if ( a !== b ) { return 0 ; } for ( let k = 0 ; k < 3 ; ++ k ) { if ( row [ k ] !== a || col [ k ] !== a ) { return 0 ; } } return 1 ; }; let ans = 0 ; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { ans += check ( i , j ); } } return ans ; }

1class Solution {2public:3  int numMagicSquaresInside(vector<vector<int>> &grid) {4    int m = grid.size();5    int n = grid[0].size();6    int ans = 0;7    auto check = [&](int i, int j) {8      if (i + 3 > m || j + 3 > n) {9        return 0;10      }11      vector<int> cnt(16);12      vector<int> row(3);13      vector<int> col(3);14      int a = 0, b = 0;15      for (int x = i; x < i + 3; ++x) {16        for (int y = j; y < j + 3; ++y) {17          int v = grid[x][y];18          if (v < 1 || v > 9 || ++cnt[v] > 1) {19            return 0;20          }21          row[x - i] += v;22          col[y - j] += v;23          if (x - i == y - j) {24            a += v;25          }26          if (x - i + y - j == 2) {27            b += v;28          }29        }30      }31      if (a != b) {32        return 0;33      }34      for (int k = 0; k < 3; ++k) {35        if (row[k] != a || col[k] != a) {36          return 0;37        }38      }39      return 1;40    };41    for (int i = 0; i < m; ++i) {42      for (int j = 0; j < n; ++j) {43        ans += check(i, j);44      }45    }46    return ans;47  }48};

1class Solution:2    def numMagicSquaresInside(self, grid: List[List[int]]) -> int: def check(i: int, j: int) -> int: if i + 3 > m or j + 3 > n: return 0 s = set() row = [0] * 3 col = [0] * 3 a = b = 0 for x in range(i, i + 3): for y in range(j, j + 3): v = grid[x][y] if v < 1 or v > 9: return 0 s . add(v) row[x - i] += v col[y - j] += v if x - i == y - j: a += v if x - i == 2 - (y - j): b += v if len(s) != 9 or a != b: return 0 if any(x != a for x in row) or any(x != a for x in col): return 0 return 1 m, n = len(grid), len(grid[0]) return sum(check(i, j) for i in range(m) for j in range(n))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem