Domain 2MediumMEDIUM

Magic Squares In Grid

Iterate through all possible top-left corners of a 3x3 subgrid. For each, validate distinctness (set), range [1-9], and sum properties (rows/cols/diagonals = 15).

Domain: medium•Updated: 2026-09-02
#Brute-Force#Set#O(R*C)#O(1)

Problem Breakdown

The goal is to count the number of 3×33 \times 3 subgrids within a larger grid that satisfy the definition of a “magic square.” A magic square has two strict requirements:

  1. Content: It must contain exactly the integers 1 through 9, each appearing once (distinct). No zeros, no duplicates, and no numbers outside this range are allowed in the subgrid.
  2. Sum Property: The sum of every row, column, and both diagonals within that 3×33 \times 3 block must be equal. Given the content constraint (1 to 9), the total sum is fixed at 45, meaning each line (row/col/diag) must sum to exactly 15.

Intuition

Since a magic square has specific properties, we can validate candidates efficiently:

  • Constraints: The grid dimensions are small (N≤10N \le 10), allowing an O(R×C)O(R \times C) approach where every cell is visited.
  • Validation Order: It is crucial to check the content (distinctness and range) before checking sums. If a subgrid contains duplicates or numbers outside 1-9, it cannot be a magic square regardless of its sum. This allows for “early pruning” inside the helper function, returning False immediately upon finding an invalid value.
  • Sum Check: Once distinctness and range are confirmed (implying the set is {1..9}), we only need to verify that all rows, columns, and diagonals sum to 15. If they do not, it fails the magic square property.

Approach

We iterate through every possible top-left coordinate (r,c)(r, c) of a 3×33 \times 3 subgrid within the bounds of the input grid (0≤r<R−20 \le r < R - 2, 0≤c<C−20 \le c < C - 2). For each candidate:

  1. Content Validation: Extract all 9 elements into a set or check them on-the-fly to ensure they are between 1 and 9 inclusive, and that no duplicates exist within the subgrid. If any violation occurs, discard immediately.
  2. Sum Validation: Calculate sums for each of the three rows, three columns, and two diagonals. Verify all equal 15. Note: Since we enforced distinctness {1..9}, checking against 15 is mathematically sufficient to ensure equality among lines (if one row was different, another would likely be too or total sum wouldn’t match).
  3. Counting: If both validations pass, increment the counter.

Complexity Analysis

  • Time Complexity: O(R×C)O(R \times C), where RR is rows and CC is columns. We iterate through every possible top-left corner of a subgrid ((R−2)×(C−2)(R-2) \times (C-2)). For each candidate, we perform constant work proportional to the fixed size of the magic square (3×3=93 \times 3 = 9 cells). Thus, it scales linearly with input dimensions.
  • Space Complexity: O(1)O(1) auxiliary space. We use a set seen which holds at most 9 integers and variables for sums/indices. The grid itself is not modified or cloned significantly beyond the current subgrid access.

Solution

class Solution:
    def numMagicSquaresInside(self, grid):
        """
        Counts the number of 3x3 magic square subgrids in a given integer grid.
        
        A valid magic square must contain distinct numbers from 1 to 9 
        and have equal sums for all rows, columns, and diagonals (which implies sum=15).
        """
        if not grid or len(grid) < 3:
            return 0
        
        R = len(grid)
        C = len(grid[0])
        
        count = 0
        
        # Iterate over all possible top-left corners of a 3x3 subgrid
        for r in range(R - 2):
            for c in range(C - 2):
                if self.is_magic_square(grid, r, c):
                    count += 1
                    
        return count

    def is_magic_square(self, grid, start_r, start_c):
        """Helper to validate a specific 3x3 subgrid starting at (start_r, start_c)."""
        
        seen = set()
        
        # Check all cells for distinctness and range [1-9]
        for i in range(3):
            row_sum_i = 0
            col_idx_offset = start_c
            
            for j in range(3):
                val = grid[start_r + i][start_c + j]
                
                # Constraint: Must be between 1 and 9 inclusive. 
                if not (1 <= val <= 9) or val in seen:
                    return False
                
                seen.add(val)
        
        # If we reach here, distinctness and [1-9] are satisfied. 
        # Since sum(1..9) = 45, target row/col/diag sum must be 15.
        
        for i in range(3):
            if grid[start_r + i][start_c] + \
               grid[start_r + i][start_c+1] + \
               grid[start_r + i][start_c+2] != 15: 
                return False
            
        # Check columns
        for j in range(3):
            s = (grid[start_r][start_c+j] + 
                  grid[start_r+1][start_c+j] + 
                  grid[start_r+2][start_c+j])
            if s != 15: return False
            
        # Check diagonals
        d1 = grid[start_r][start_c] + \
             grid[start_r+1][start_c+1] + \
             grid[start_r+2][start_c+2]
        
        d2 = grid[start_r][start_c+2] + \
             grid[start_r+1][start_c+1] + \
             grid[start_r+2][start_c]
             
        if d1 != 15 or d2 != 15: return False
        
        return True

Edge Cases Handled

  • Empty/Small Grid: The main loop checks len(grid) < 3 and the range loops naturally handle grids smaller than 3×33 \times 3 by not entering the inner logic.
  • Invalid Values (0 or >9): Explicitly checked in is_magic_square. If a value is outside [1, 9], it returns False immediately.
  • Duplicates: The seen set ensures that if any number repeats within the 3×33 \times 3 block, validation fails.
  • Sum Mismatch: Even with distinct numbers 1-9, sums must equal 15. If rows/cols/diagonals sum to something else (e.g., due to permutation error), it returns False.