Magic Squares In Grid

Medium
915.

Magic Squares In Grid

Magic Squares In Grid is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google and Infosys interviews.

A 3 × 3 magic square is a grid holding each of the digits 1 to 9 exactly once, where every row, every column and both diagonals add up to the same total.

Given a grid of integers, count how many 3 × 3 contiguous subgrids are magic squares.

Example 1

Input
grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output
1
Explanation
The left 3 × 3 block is magic; the right one is not.

Example 2

Input
grid = [[8]]
Output
0
Explanation
Too small to hold a 3 × 3 block.

Example 3

Input
grid = [[4,3,8],[9,5,1],[2,7,6]]
Output
1

Constraints

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 10
  • 0 <= grid[i][j] <= 15
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var numMagicSquaresInside = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Magic Squares In Grid — Solution in Python, Java & C++

Magic Squares In Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Magic Squares In Grid is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google and Infosys interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon, Google, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A 3 × 3 magic square is a grid holding each of the digits 1 to 9 exactly once, where every row, every column and both diagonals add up to the same total.

Given a grid of integers, count how many 3 × 3 contiguous subgrids are magic squares.

Example 1

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: The left 3 × 3 block is magic; the right one is not.

Example 2

Input: grid = [[8]]
Output: 0
Explanation: Too small to hold a 3 × 3 block.

Example 3

Input: grid = [[4,3,8],[9,5,1],[2,7,6]]
Output: 1

Constraints

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

Hints for Magic Squares In Grid

  1. Hint 1

    There are at most (row - 2) · (col - 2) candidate blocks, so checking each one in full is cheap.

  2. Hint 2

    First reject any block that does not hold exactly the digits 1 through 9.

  3. Hint 3

    A 3 × 3 magic square always sums to 15 on every line.

How to solve Magic Squares In Grid

The grid is tiny, so try every 3 × 3 position and validate it directly. Validation is two parts: the digit set, then the eight line sums.

Approach

  1. For each top-left corner, mark the nine values and reject unless they are exactly 1 … 9, each once.
  2. Check the three row sums, the three column sums and the two diagonals all equal 15.
  3. Count the blocks that pass.

Why it works

The total of 1 … 9 is 45, and the three rows partition the square, so if all rows are equal each must be 15 — the constant is forced, not a choice. Checking the digit set first is what makes the rest safe: without it a block of nine 5s passes every sum test.

Complexity

  • Time — O(row · col)
  • Space — O(1)

Pitfalls

  • Skipping the distinctness check accepts grids of all 5s.
  • Both diagonals matter, not just the main one.
  • Values outside 1 … 9 (including 0) disqualify a block immediately.

Reference solution

Python

from typing import List

def numMagicSquaresInside(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    def magic(r: int, c: int) -> bool:
        vals = [grid[r + i][c + j] for i in range(3) for j in range(3)]
        if sorted(vals) != [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            return False
        for i in range(3):
            if grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15:
                return False
            if grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15:
                return False
        if grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15:
            return False
        if grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15:
            return False
        return True

    return sum(1 for r in range(m - 2) for c in range(n - 2) if magic(r, c))

Java

public static int numMagicSquaresInside(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int count = 0;
    for (int r = 0; r + 2 < m; r++) {
        for (int c = 0; c + 2 < n; c++) if (magicAt(grid, r, c)) count++;
    }
    return count;
}

private static boolean magicAt(int[][] grid, int r, int c) {
    boolean[] seen = new boolean[10];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int v = grid[r + i][c + j];
            if (v < 1 || v > 9 || seen[v]) return false;
            seen[v] = true;
        }
    }
    for (int i = 0; i < 3; i++) {
        if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15) return false;
        if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15) return false;
    }
    if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15) return false;
    if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15) return false;
    return true;
}

C++

static bool magicAt(vector<vector<int>>& grid, int r, int c) {
    bool seen[10] = { false };
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int v = grid[r + i][c + j];
            if (v < 1 || v > 9 || seen[v]) return false;
            seen[v] = true;
        }
    }
    for (int i = 0; i < 3; i++) {
        if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15) return false;
        if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15) return false;
    }
    if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15) return false;
    if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15) return false;
    return true;
}

int numMagicSquaresInside(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    int count = 0;
    for (int r = 0; r + 2 < m; r++) {
        for (int c = 0; c + 2 < n; c++) if (magicAt(grid, r, c)) count++;
    }
    return count;
}

JavaScript

var numMagicSquaresInside = function(grid) {
    var m = grid.length, n = grid[0].length;
    var magic = function(r, c) {
        var seen = [];
        var i, j;
        for (i = 0; i <= 9; i++) seen.push(0);
        for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
                var v = grid[r + i][c + j];
                if (v < 1 || v > 9 || seen[v]) return false;
                seen[v] = 1;
            }
        }
        for (i = 0; i < 3; i++) {
            if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] !== 15) return false;
            if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] !== 15) return false;
        }
        if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] !== 15) return false;
        if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] !== 15) return false;
        return true;
    };
    var count = 0;
    for (var r = 0; r + 2 < m; r++) {
        for (var c = 0; c + 2 < n; c++) if (magic(r, c)) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal