840. Magic Squares In Grid

Problem Description

A magic square is a grid where the sum of the numbers in each row, each column, and both diagonals are the same. In this particular problem, we deal with 3 x 3 magic squares, which mean the grid should be filled with distinct numbers from 1 to 9 inclusive. We are given a larger grid (of size row x col) and need to find how many 3 x 3 subgrids within this larger grid qualify as magic squares. A subgrid is defined as contiguous, meaning it consists of neighboring elements from the original grid.

To summarize, our task is to find & count all 3 x 3 subgrids in the given grid that satisfy the conditions of a magic square.

Intuition

The most straightforward approach to solve this problem is to check every possible 3 x 3 subgrid in the larger grid. For each subgrid, we need to verify if it is a magic square. To do that, we need to:

Make sure that the numbers are all distinct and within the range of 1 to 9.
Check that the sums of the rows, columns, and diagonals are the same.

Given that we are to scan a row x col grid, we'd start at the top-left corner and move through the grid, checking each 3 x 3 subgrid. Since you can't have a 3 x 3 subgrid beyond the point where there are fewer than 3 rows or columns left, we stop the search before reaching the right and bottom edges of the grid.

For each 3 x 3 subgrid:

We validate that all numbers are distinct and within the range 1 to 9 using a set.
We calculate the sums of each row, each column, and both diagonals.
Then, we check if these sums are all equal to one another.

This is done by taking one of these sums as a reference — typically, the sum of the first row or the first diagonal — and comparing all other sums against this reference sum.

If any condition fails, we immediately return 0 for that subgrid, implying it is not a magic square. If all conditions pass, then we have found a magic square, and we return 1. The final answer is obtained by summing these values for each possible subgrid in the grid, which gives the total number of 3 x 3 magic square subgrids.

Learn more about Math patterns.

Solution Approach

The solution follows a brute-force approach where we systematically check all possible 3 x 3 subgrids in the given row x col grid. Here's a step-by-step explanation of the implementation:

Check Function: We define a helper function named check(i, j) which checks if the 3 x 3 subgrid starting at position (i, j) in the larger grid is a magic square.
Boundary Check: This function first confirms that the subgrid does not go out of the boundaries of the row x col grid. If (i + 3) exceeds m (number of rows) or (j + 3) exceeds n (number of columns), we immediately return 0 as it does not qualify as a 3 x 3 subgrid.
Unique and In-range Values: We use a set s to store the values and ensure all numbers are distinct and within the range from 1 to 9. If any number is found out of this range, or if we encounter a duplicate, we return 0.
Calculating Sums: We initialize row and col arrays to store the sums of each row and each respective column, and two variables a and b to store the sums of the two diagonals. As we fill in these with the values from the subgrid, we check for diagonals explicitly by comparing indices.
Equality of Sums: Once we have stored all sums, we then check if these sums are equal. We compare all row and col sums against the sum of one of the diagonals a, and also check if the two diagonal sums a and b are equal. If all sums are equal, it is a magic square; otherwise, we return 0.
Iterate Through Grid: In the main part of the solution, we iterate through the entire row x col grid using nested loops, invoking the check function on each possible starting position (i, j) for a subgrid.
Sum of Magic Squares: We sum the results of the check function calls across all possible positions. The sum represents the total count of 3 x 3 magic squares found within the larger grid.

In terms of algorithms and data structures, this problem is tackled using a simple brute force algorithm that iterates through all elements utilizing basic control structures (loops and conditionals). The use of a set ensures that all values within a subgrid are distinct, and arrays are used to track the sums of rows and columns which makes checking the sum conditions efficient.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are given the following grid of size 4x4:

We want to find all possible 3x3 subgrids that are magic squares.

Starting at the top-left corner, with the initial subgrid being:

4  3  8
9  5  1
2  7  6

We call the check(0, 0) function to check this subgrid.
Within the check function, we ensure it's within the grid's boundary. Since we are starting at (0, 0), no boundary issues arise here.
Now we check if all numbers are in the range [1, 9] and are distinct. We add the numbers into a set s. If the set's size is less than 9 after insertion, we have duplicates, which is not the case here.
We calculate the sums of rows, columns, and diagonals:
- Row sums: [15, 15, 15]
- Column sums: [15, 15, 15]
- Diagonal sums: a = 15 (4+5+6), b = 15 (8+5+2)
We compare all sums against one another. Since they are all equal to 15, this subgrid is a magic square.
Move to the next subgrid by sliding one column to the right:

3  8  1
5  1  2
7  6  3

Call check(0, 1) and repeat the process. This subgrid does not form a magic square as the rows, columns, and diagonal sums will not be equal.

We continue this process for all 2 possible 3x3 subgrids along the rows (as we have a 4x4 grid, there is no space for more than two 3x3 subgrids horizontally), and then repeat for the subsequent rows until we reach the bottom of the grid.

In the example grid above, there is only one magic square, the very first subgrid we checked. Thus, the function would ultimately return a total count of 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
5        def is_magic_square(x: int, y: int) -> bool:
6            # Check if the square starting at (x, y) is a 3x3 magic square
7          
8            # Ensure that the square does not go out of bounds
9            if x + 3 > row_count or y + 3 > column_count:
10                return False
11          
12            unique_values = set()
13            row_sums = [0] * 3
14            column_sums = [0] * 3
15            diagonal_sum_lr = 0  # Left-to-right diagonal
16            diagonal_sum_rl = 0  # Right-to-left diagonal
17          
18            for i in range(x, x + 3):
19                for j in range(y, y + 3):
20                    value = grid[i][j]
21                  
22                    # Ensure the value is unique and within the range 1-9
23                    if value < 1 or value > 9:
24                        return False
25                    unique_values.add(value)
26                  
27                    # Update sums of rows and columns
28                    row_sums[i - x] += value
29                    column_sums[j - y] += value
30                  
31                    # Update diagonal sums
32                    if i - x == j - y:
33                        diagonal_sum_lr += value
34                    if i - x == 2 - (j - y):
35                        diagonal_sum_rl += value
36          
37            # Check uniqueness of values (magic square has distinct values 1-9)
38            if len(unique_values) != 9:
39                return False
40          
41            # Check the sums of the diagonals, rows, and columns for equality
42            if diagonal_sum_lr != diagonal_sum_rl:
43                return False
44            if any(row_sum != diagonal_sum_lr for row_sum in row_sums):
45                return False
46            if any(column_sum != diagonal_sum_lr for column_sum in column_sums):
47                return False
48          
49            # It's a magic square if all checks passed
50            return True
51
52        # Total number of rows and columns
53        row_count, column_count = len(grid), len(grid[0])
54      
55        # Accumulate the count of magic squares found in the grid
56        magic_squares_count = 0
57        for i in range(row_count):
58            for j in range(column_count):
59                magic_squares_count += is_magic_square(i, j)
60      
61        return magic_squares_count
62
63# Example usage:
64# solution = Solution()
65# result = solution.numMagicSquaresInside([[4,3,8,4], [9,5,1,9], [2,7,6,2]])
66# print(result)  # Output will be the number of 3x3 magic squares inside the given grid
67

1class Solution {
2    private int rows;
3    private int cols;
4    private int[][] grid;
5
6    // Method for finding the number of magic squares inside the given grid
7    public int numMagicSquaresInside(int[][] grid) {
8        rows = grid.length;
9        cols = grid[0].length;
10        this.grid = grid;
11        int count = 0;
12      
13        // Iterate over all possible 3x3 sub-grids
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                count += checkMagicSquare(i, j);
17            }
18        }
19        return count;
20    }
21
22    // Helper method to check if the 3x3 sub-grid starting at (i, j) is a magic square
23    private int checkMagicSquare(int i, int j) {
24        // Check if the sub-grid exceeds the boundary of the grid
25        if (i + 3 > rows || j + 3 > cols) {
26            return 0;
27        }
28
29        // Check uniqueness of numbers and calculate sums of rows, columns, and diagonals
30        int[] frequency = new int[16];
31        int[] rowSum = new int[3];
32        int[] colSum = new int[3];
33        int diagonalSum = 0, antiDiagonalSum = 0;
34        for (int x = i; x < i + 3; ++x) {
35            for (int y = j; y < j + 3; ++y) {
36                int value = grid[x][y];
37                // Check if the value is in the 1-9 range and its uniqueness within the sub-grid
38                if (value < 1 || value > 9 || ++frequency[value] > 1) {
39                    return 0;
40                }
41                rowSum[x - i] += value;
42                colSum[y - j] += value;
43                // Diagonal sum
44                if (x - i == y - j) {
45                    diagonalSum += value;
46                }
47                // Anti-diagonal sum
48                if (x - i + y - j == 2) {
49                    antiDiagonalSum += value;
50                }
51            }
52        }
53
54        // Check if the diagonal sums are equal
55        if (diagonalSum != antiDiagonalSum) {
56            return 0;
57        }
58
59        // Check if each row and column sums up to the value of the diagonal sum
60        for (int k = 0; k < 3; ++k) {
61            if (rowSum[k] != diagonalSum || colSum[k] != diagonalSum) {
62                return 0;
63            }
64        }
65
66        // The grid is a magic square if all checks pass
67        return 1;
68    }
69}
70

1class Solution {
2public:
3    int numMagicSquaresInside(vector<vector<int>>& grid) {
4        int rows = grid.size();    // total number of rows in the grid
5        int cols = grid[0].size(); // total number of columns in the grid
6        int magicSquareCount = 0;  // counter for magic squares
7
8        // Lambda function to check if the 3x3 grid with top-left corner at (i, j) is a magic square
9        auto isMagicSquare = [&](int i, int j) -> int {
10            // Check if the square extends beyond the grid boundaries
11            if (i + 3 > rows || j + 3 > cols) {
12                return 0;
13            }
14          
15            vector<int> count(16, 0); // Counter for numbers 1 to 9 within the 3x3 grid
16            vector<int> sumRow(3, 0); // Sum of each row within the 3x3 grid
17            vector<int> sumCol(3, 0); // Sum of each column within the 3x3 grid
18            int diagSum1 = 0;         // Sum of the first diagonal
19            int diagSum2 = 0;         // Sum of the second diagonal
20          
21            // Iterate over the 3x3 grid and populate sums and counts
22            for (int x = i; x < i + 3; ++x) {
23                for (int y = j; y < j + 3; ++y) {
24                    int value = grid[x][y];
25                    // Check for invalid numbers or duplicates
26                    if (value < 1 || value > 9 || ++count[value] > 1) {
27                        return 0;
28                    }
29                    // Update row and column sums
30                    sumRow[x - i] += value;
31                    sumCol[y - j] += value;
32                    // Update diagonal sums
33                    if (x - i == y - j) {
34                        diagSum1 += value;
35                    }
36                    if (x - i + y - j == 2) {
37                        diagSum2 += value;
38                    }
39                }
40            }
41          
42            // Check if both diagonals have the same sum
43            if (diagSum1 != diagSum2) {
44                return 0;
45            }
46          
47            // Check if each row and column sum to the same value as the diagonals
48            for (int k = 0; k < 3; ++k) {
49                if (sumRow[k] != diagSum1 || sumCol[k] != diagSum1) {
50                    return 0;
51                }
52            }
53          
54            // If all checks pass, it's a magic square
55            return 1;
56        };
57      
58        // Iterate over each possible 3x3 grid in the grid to count magic squares
59        for (int i = 0; i < rows; ++i) {
60            for (int j = 0; j < cols; ++j) {
61                magicSquareCount += isMagicSquare(i, j);
62            }
63        }
64      
65        return magicSquareCount; // Return the total count of magic squares
66    }
67};
68

1// Counts the number of 3x3 magic squares within a 2D grid.
2function numMagicSquaresInside(grid: number[][]): number {
3    const numRows = grid.length;       // Represents the number of rows in the grid.
4    const numCols = grid[0].length;   // Represents the number of columns in the grid.
5
6    // Checks if a 3x3 subgrid starting at position (row, col) is a magic square.
7    // Returns 1 if it's a magic square, otherwise returns 0.
8    const isMagicSquare = (row: number, col: number): number => {
9        // Boundary check to ensure there's a 3x3 subgrid.
10        if (row + 3 > numRows || col + 3 > numCols) {
11            return 0;
12        }
13
14        // Check for unique values between 1 and 9 using a frequency array.
15        const frequency: number[] = new Array(16).fill(0);
16        // Sum of each row in the 3x3 subgrid.
17        const rowSums: number[] = new Array(3).fill(0);
18        // Sum of each column in the 3x3 subgrid.
19        const colSums: number[] = new Array(3).fill(0);
20      
21        let diagonalSum1 = 0; // Sum of the primary diagonal.
22        let diagonalSum2 = 0; // Sum of the secondary diagonal.
23
24        // Iterate over the 3x3 subgrid.
25        for (let x = row; x < row + 3; ++x) {
26            for (let y = col; y < col + 3; ++y) {
27                const value = grid[x][y];
28
29                // Check for valid values and duplicates.
30                if (value < 1 || value > 9 || ++frequency[value] > 1) {
31                    return 0;
32                }
33
34                // Calculate running sum of current row and column.
35                rowSums[x - row] += value;
36                colSums[y - col] += value;
37              
38                // Check if the current cell is on the primary diagonal.
39                if (x - row === y - col) {
40                    diagonalSum1 += value;
41                }
42                // Check if the current cell is on the secondary diagonal.
43                if (x - row === 2 - (y - col)) {
44                    diagonalSum2 += value;
45                }
46            }
47        }
48
49        // Ensure both diagonals have the same sum.
50        if (diagonalSum1 !== diagonalSum2) {
51            return 0;
52        }
53
54        // Check if each row and column have the same sum as the diagonals.
55        for (let k = 0; k < 3; ++k) {
56            if (rowSums[k] !== diagonalSum1 || colSums[k] !== diagonalSum1) {
57                return 0;
58            }
59        }
60
61        // If all checks are passed, it's a magic square.
62        return 1;
63    };
64
65    // Initialize the count of magic squares found.
66    let magicSquareCount = 0;
67
68    // Iterate over every possible top-left position of a 3x3 subgrid in the grid.
69    for (let i = 0; i < numRows; ++i) {
70        for (let j = 0; j < numCols; ++j) {
71            // Increment count if a magic square is found.
72            magicSquareCount += isMagicSquare(i, j);
73        }
74    }
75
76    // Return the total count of magic squares.
77    return magicSquareCount;
78}
79

Time and Space Complexity

Time Complexity

The time complexity of the given code is dictated by the nested loops that iterate over every 3x3 subgrid within the m x n grid, and the checks performed for each subgrid.

It has two outer loops that iterate over each cell in the grid. In the worst case scenario (where the grid is filled with 3x3 subgrids), these loops run in O(m * n) time.
For each cell (i, j), the check function is called. This function itself contains two nested loops which run a fixed number of times (9 iterations, since they iterate over the 3x3 subgrid). Therefore, they contribute a constant time factor O(1).
Within the check function, operations such as addition, set addition, and conditional checks are performed in constant time.
The final check for unique numbers and sums of rows, columns, and diagonals also takes constant time, since it involves iterating over fixed-size lists (size 3) and a set of size 9.

Putting it all together, the overall time complexity of the algorithm is O(m * n) due to the initial loops over the grid that check for magic squares in each subgrid.

Space Complexity

The space complexity is determined by the extra space used by the algorithm, which includes:

The set s, which contains up to 9 integers to ensure uniqueness within each 3x3 subgrid.
The row and col arrays, each of size 3, used to track the sum of the numbers in each row and column of the subgrid.
Variables a and b used for diagonal sums.

Notably, all of these are of fixed size and do not scale with the size of the input grid.

Therefore, the space complexity is O(1), as the auxiliary space required remains constant regardless of the input size.

The main source of space consumption is the input itself, which is O(m * n), but this isn't counted towards auxiliary space complexity as it is not additional space used by the algorithm.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: