Magic Squares In Grid solution and explanation
Infosys
Google
9 more videos on this problem
Magic Squares In Grid - Leetcode 840 - PythonNeetCodeIO · 21:12 · 15K views
Magic Squares In Grid | Hashmap | Leetcode 840Techdose · 11:49 · 1K views
LeetCode 840 - Magic Squares In Grid - JavaAlpha-Code · 13:39 · 500 views
840. Magic Squares In Grid | Leetcode Daily - PythonLeetcode Daily · 9:20 · 335 views
Magic Squares In Grid | Leetcode 840 | Java Code | Developer CoderDeveloper Coder · 10:17 · 197 views
Magic Squares In Grid - Leetcode 840 - JavaCode With K5KC · 17:25 · 154 views
840. Magic Squares In Grid | Matrix | LeetCode | Full ExplanationCodeInBits · 18:54 · 138 views
What Makes a 3×3 Grid a Magic Square | 840. Magic Squares In Grid | LeetCode DailyDaily Dose Of LeetCode · 14:19 · 83 views
LeetCode 840: Magic Squares In Grid | Java Solution | Matrix TraversalCode Scribbler · 6:22 · 71 views
840. Magic Squares In Grid | Matrix | Math | Greedy | LeetCode | MediumLeet's Code · 13:05 · 60 views
The problem
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] <= 15
Approach overview
Problem Overview: You are given a matrix and must count how many 3x3 subgrids form a magic square. A valid magic square contains the digits 1-9 exactly once, and every row, column, and both diagonals sum to the same value (15 for a 3x3 grid).
Approach 1: Brute Force and Check Conditions (O(m*n) time, O(1) space)
Scan every possible 3x3 subgrid using two nested loops. For each starting position (i, j), extract the nine values and validate the magic square conditions. First verify that all digits are between 1 and 9 and appear exactly once using a small boolean array or hash table. Then compute the sums of all three rows, three columns, and the two diagonals. If all sums match (15), the subgrid is valid.
This approach works because the grid size checked each time is fixed (3x3). Even though multiple checks are performed, they are constant operations. The algorithm iterates across the grid once, giving overall O(m*n) time with constant extra space.
Approach 2: Pattern Matching Optimization (O(m*n) time, O(1) space)
A key property of every 3x3 magic square using digits 1-9 is that the center must always be 5. Additionally, the corners and edges follow specific rotation patterns such as 4,9,2,7,6,1,8,3. Instead of computing every sum, you first check whether the center cell equals 5. If not, the subgrid cannot be a magic square.
Next, read the outer ring of the 3x3 grid and compare it against known cyclic patterns representing valid magic squares and their rotations. This avoids repeated row/column calculations and quickly filters invalid candidates. The algorithm still scans all possible positions in the matrix, so the time complexity remains O(m*n), but the constant work per check is smaller.
This pattern-based validation relies on mathematical properties of magic squares, making it a clever application of math and symmetry recognition.
Recommended for interviews: Start with the brute force validation approach. It clearly demonstrates your understanding of magic square rules and grid traversal. After that, mention the pattern insight (center equals 5 and cyclic edge patterns). Interviewers value candidates who first implement the straightforward solution and then recognize the mathematical optimization.
Approach 1: Brute Force and Check Conditions
This 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.
def is_magic_square(grid, row, col):
nums = [grid[row+i][col+j] for i in range(3) for j in range(3)]
if sorted(nums) != list(range(1, 10)):
return False
return (sum(grid[row][col:col+3]) ==
sum(grid[row+1][col:col+3]) ==
sum(grid[row+2][col:col+3]) ==
sum(grid[row+i][col] for i in range(3)) ==
sum(grid[row+i][col+1] for i in range(3)) ==
sum(grid[row+i][col+2] for i in range(3)) ==
grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] ==
grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col])
def num_magic_squares_inside(grid):
count = 0
for i in range(len(grid) - 2):
for j in range(len(grid[0]) - 2):
if is_magic_square(grid, i, j):
count += 1
return count
grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
print(num_magic_squares_inside(grid)) # Output: 1#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isMagicSquare(const vector<vector<int>>& grid, int row, int col) {
vector<int> nums;
for (int i = row; i < row + 3; ++i) {
for (int j = col; j < col + 3; ++j) {
nums.push_back(grid[i][j]);
}
}
sort(nums.begin(), nums.end());
if (nums != vector<int>({1, 2, 3, 4, 5, 6, 7, 8, 9})) return false;
int target = grid[row][col] + grid[row][col+1] + grid[row][col+2];
for (int i = 0; i < 3; ++i) {
if (grid[row+i][col] + grid[row+i][col+1] + grid[row+i][col+2] != target ||
grid[row][col+i] + grid[row+1][col+i] + grid[row+2][col+i] != target)
return false;
}
return (grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] == target &&
grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] == target);
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i <= grid.size() - 3; ++i) {
for (int j = 0; j <= grid[0].size() - 3; ++j) {
if (isMagicSquare(grid, i, j)) ++count;
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
cout << numMagicSquaresInside(grid); // Output: 1
return 0;
}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.
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.
Approach 2: Using Pattern Matching
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.
import java.util.HashSet;
import java.util.Set;
public class MagicSquares {
public static boolean isMagicSquare(int[][] grid, int row, int col) {
Set<Integer> nums = new HashSet<>();
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
nums.add(grid[i][j]);
}
}
if (nums.size() != 9 || nums.stream().anyMatch(n -> n < 1 || n > 9)) return false;
return (grid[row+1][col+1] == 5 && grid[row][col] + grid[row][col+1] + grid[row][col+2] == 15 &&
grid[row+2][col] + grid[row+2][col+1] + grid[row+2][col+2] == 15 &&
grid[row][col] + grid[row+1][col] + grid[row+2][col] == 15 &&
grid[row][col+2] + grid[row+1][col+2] + grid[row+2][col+2] == 15 &&
grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] == 15 &&
grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] == 15);
}
public static int numMagicSquaresInside(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length - 2; i++) {
for (int j = 0; j < grid[0].length - 2; j++) {
if (isMagicSquare(grid, i, j)) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[][] grid = {{4,3,8,4},{9,5,1,9},{2,7,6,2}};
System.out.println(numMagicSquaresInside(grid)); // Output: 1
}
}function isMagicSquare(grid, row, col) {
let nums = new Set();
for (let i = row; i < row + 3; i++) {
for (let j = col; j < col + 3; j++) {
nums.add(grid[i][j]);
}
}
if (nums.size !== 9 || [...nums].some(n => n < 1 || n > 9)) return false;
return (grid[row+1][col+1] === 5 && grid[row][col] + grid[row][col+1] + grid[row][col+2] === 15 &&
grid[row+2][col] + grid[row+2][col+1] + grid[row+2][col+2] === 15 &&
grid[row][col] + grid[row+1][col] + grid[row+2][col] === 15 &&
grid[row][col+2] + grid[row+1][col+2] + grid[row+2][col+2] === 15 &&
grid[row][col] + grid[row+1][col+1] + grid[row+2][col+2] === 15 &&
grid[row][col+2] + grid[row+1][col+1] + grid[row+2][col] === 15);
}
function numMagicSquaresInside(grid) {
let count = 0;
for (let i = 0; i < grid.length - 2; i++) {
for (let j = 0; j < grid[0].length - 2; j++) {
if (isMagicSquare(grid, i, j)) {
count++;
}
}
}
return count;
}
const grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]];
console.log(numMagicSquaresInside(grid)); // Output: 1In this Java approach, a Set is used to collect numbers in the subgrid to check uniqueness and if they contain numbers between 1 and 9 only. The pivotal grid checking is simplified by pattern checks as previously mentioned, making the checks concise and optimized.
Time complexity: O(n*m), similar to the straightforward approach with subtle optimizations.
Space complexity: O(1), utilizing a fixed hash set but not growing with input size.
Approach 3: Enumeration
We directly enumerate the top-left coordinates (i, j) of each 3 times 3 submatrix, then check whether the submatrix satisfies the "magic square" property. If so, we increment the answer by one. After the enumeration, we return the answer.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
function numMagicSquaresInside(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const check = (i: number, j: number): number => {
if (i + 3 > m || j + 3 > n) {
return 0;
}
const cnt: number[] = Array(16).fill(0);
const row: number[] = Array(3).fill(0);
const col: number[] = 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;
}func numMagicSquaresInside(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
check := func(i, j int) int {
if i+3 > m || j+3 > n {
return 0
}
cnt := [16]int{}
row := [3]int{}
col := [3]int{}
a, b := 0, 0
for x := i; x < i+3; x++ {
for y := j; y < j+3; y++ {
v := grid[x][y]
if v < 1 || v > 9 || cnt[v] > 0 {
return 0
}
cnt[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 a != b {
return 0
}
for k := 0; k < 3; k++ {
if row[k] != a || col[k] != a {
return 0
}
}
return 1
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
ans += check(i, j)
}
}
return
}impl Solution {
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut ans: i32 = 0;
let check = |i: usize, j: usize, grid: &Vec<Vec<i32>>| -> i32 {
if i + 3 > m || j + 3 > n {
return 0;
}
let mut cnt = vec![0; 16];
let mut row = vec![0; 3];
let mut col = vec![0; 3];
let mut a = 0;
let mut b = 0;
for x in i..i + 3 {
for y in j..j + 3 {
let v = grid[x][y] as usize;
if v < 1 || v > 9 {
return 0;
}
cnt[v] += 1;
if cnt[v] > 1 {
return 0;
}
let vv = grid[x][y];
row[x - i] += vv;
col[y - j] += vv;
if x - i == y - j {
a += vv;
}
if x - i + y - j == 2 {
b += vv;
}
}
}
if a != b {
return 0;
}
for k in 0..3 {
if row[k] != a || col[k] != a {
return 0;
}
}
1
};
for i in 0..m {
for j in 0..n {
ans += check(i, j, &grid);
}
}
ans
}
}Complexity comparison
| 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), similar to the straightforward approach with subtle optimizations. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force and Check Conditions | O(m*n) | O(1) | Best general approach. Easy to implement and clearly validates all magic square rules. |
| Pattern Matching Optimization | O(m*n) | O(1) | When you know the mathematical properties of 3x3 magic squares and want fewer checks per subgrid. |
Frequently asked questions
Is Magic Squares In Grid easy or hard?
Magic Squares In Grid is classified as a Medium problem on LeetCode. The matrix traversal is straightforward, but recognizing the magic square constraints and implementing efficient validation requires careful checks.
Magic Squares In Grid Python/Java solution
Python, Java, C++, and JavaScript implementations follow the same idea: iterate through every 3x3 subgrid, validate digit uniqueness, and confirm equal sums across rows, columns, and diagonals. Optimized implementations also check that the center cell is 5 before running full validation.
How to solve Magic Squares In Grid in O(n)?
Treat the grid scan as O(m*n) and validate each 3x3 region in constant time. Use a digit presence check for numbers 1–9 and verify that row, column, and diagonal sums equal 15. Some optimized solutions also check that the center cell equals 5 to quickly discard invalid candidates.
What is the best approach for Magic Squares In Grid?
The best practical approach scans every 3x3 subgrid and validates magic square rules. Check that digits 1–9 appear exactly once and verify that all rows, columns, and diagonals sum to 15. This runs in O(m*n) time because each 3x3 check is constant work.
Is Magic Squares In Grid asked at Google/Amazon/Meta?
Magic square and grid validation problems appear in interviews at large tech companies, including Google and Amazon, especially in variations involving matrix traversal and pattern validation. The problem tests array handling, matrix iteration, and basic mathematical reasoning.
What data structure is used in Magic Squares In Grid?
The solution primarily uses arrays or matrices for traversal. A small boolean array or hash set is often used to verify that digits 1–9 appear exactly once inside the 3x3 subgrid.
What is the time complexity of Magic Squares In Grid?
The time complexity is O(m*n), where m and n are the grid dimensions. The algorithm checks each possible 3x3 subgrid once, and validation involves a constant number of operations since the subgrid size is fixed.