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.
Which data structure is used in a depth first search?
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 colgrid. If(i + 3)exceedsm(number of rows) or(j + 3)exceedsn(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
sto 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
rowandcolarrays to store the sums of each row and each respective column, and two variablesaandbto 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
rowandcolsums against the sum of one of the diagonalsa, and also check if the two diagonal sumsaandbare 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 colgrid using nested loops, invoking thecheckfunction on each possible starting position(i, j)for a subgrid. -
Sum of Magic Squares: We sum the results of the
checkfunction 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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we are given the following grid of size 4x4:
14 3 8 1 29 5 1 2 32 7 6 3 45 6 9 4
We want to find all possible 3x3 subgrids that are magic squares.
- Starting at the top-left corner, with the initial subgrid being:
14 3 8 29 5 1 32 7 6
-
We call the
check(0, 0)function to check this subgrid. -
Within the
checkfunction, 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)
- Row sums:
-
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:
13 8 1 25 1 2 37 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
671class 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}
701class 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};
681// 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}
79Which of the following is a min heap? 
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), thecheckfunction 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 factorO(1). - Within the
checkfunction, 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
rowandcolarrays, each of size 3, used to track the sum of the numbers in each row and column of the subgrid. - Variables
aandbused 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.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.