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.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15This approach involves iterating through each possible 3x3 subgrid within the larger grid. For each subgrid, we check if it is a magic square by validating the sum of each row, each column, and both diagonals to see if they all equal 15. Additionally, check if the subgrid contains all distinct numbers between 1 and 9. This straightforward method works well given the constraint where the largest grid size is 10x10.
This Python function first checks if the numbers in the 3x3 subgrid are exactly those between 1 and 9. If they are, it further checks if the sums of all rows, columns, and diagonals are equal to 15. The main function iterates over all possible subgrids within the main grid and counts how many are magic squares.
C++
Time complexity: O(n*m), where n and m are the number of rows and columns, respectively, since we check each 3x3 subgrid.
Space complexity: O(1), no extra space is required other than a few variables.
This approach leverages the fact that any 3x3 magic square with numbers from 1 to 9 must have specific sums for rows, columns, and diagonals. By using pattern matching, we can check if the middle element is always 5 (since the sum of 1 to 9 is 45, and any 3 rows, columns, or diagonals equate to the central element being crucial with 15/3 = 5). This limits the checks needed and optimizes the process.
This JavaScript solution checks each subgrid for being a magic square by checking preconditioned constants like the center must be 5 and the sum of borders equating to 15. By reducing unnecessary checks, efficiency is enhanced.
Java
Time complexity: O(n*m), since each subgrid must be checked.
Space complexity: O(1), since memory use is constant beyond some numeric vectors.
| Approach | Complexity |
|---|---|
| Brute Force and Check Conditions | Time complexity: O(n*m), where n and m are the number of rows and columns, respectively, since we check each 3x3 subgrid. |
| Using Pattern Matching | Time complexity: O(n*m), since each subgrid must be checked. |
3 by 3 Magic Squad | 3x3 Magic Square | Two Easy methods on 3x3 Magic Square | Magic Square 3*3 • RV TUTORIALS • 2,328,879 views views
Watch 9 more video solutions →Practice Magic Squares In Grid with our built-in code editor and test cases.
Practice on FleetCode