Jobs

Interviews

Discussions

Magic Squares In Grid

Medium

Asked by:

96 views

Topics:

Arrays

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.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

Try coding it in LeetCode

Magic Squares In Grid

Medium

Asked by:

96 views

Topics:

Arrays

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.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the bounds on the dimensions of the grid (number of rows and columns)?
Can the values within the grid be negative, zero, or non-integer?
If no 3x3 magic square exists within the grid, what should I return (e.g., 0, -1, null)?
Are all values within a potential 3x3 magic square guaranteed to be distinct integers between 1 and 9 (inclusive)?
Is it possible for a 3x3 magic square to overlap with another? (I.e., can a row/column be part of multiple magic squares)?

Brute Force Solution

Approach

The brute force approach to finding magic squares in a grid involves examining every possible small square within the larger grid. For each small square, we check if it possesses the properties of a magic square. If it does, we count it; if not, we move on to the next possible small square.

Here's how the algorithm would work step-by-step:

First, we need to consider every possible starting point for a 3x3 square inside the bigger grid.
For each starting point, we grab the 3x3 square and carefully examine its numbers.
To check if it's a magic square, we first make sure it contains only the numbers 1 through 9, and that each number appears only once.
Then, we add up the numbers in each row, each column, and both diagonals.
If all those sums are the same, then we've found a magic square, and we increase our count.
We repeat this process for every possible 3x3 square within the larger grid.
Finally, the total count of magic squares we found is our answer.

Code Implementation

def num_magic_squares_inside(grid):
    row_length = len(grid)
    column_length = len(grid[0])
    magic_square_count = 0

    for row in range(row_length - 2):
        for column in range(column_length - 2):
            # Iterate through all possible 3x3 subgrids
            if is_magic_square(grid, row, column):
                magic_square_count += 1

    return magic_square_count

def is_magic_square(grid, row, column):
    numbers = []
    for i in range(row, row + 3):
        for j in range(column, column + 3):
            numbers.append(grid[i][j])

    #Verify all digits from 1 to 9 are present
    if set(numbers) != set(range(1, 10)): 
        return False

    total = 15
    if grid[row][column] + grid[row][column+1] + grid[row][column+2] != total:
        return False
    if grid[row+1][column] + grid[row+1][column+1] + grid[row+1][column+2] != total:
        return False
    if grid[row+2][column] + grid[row+2][column+1] + grid[row+2][column+2] != total:
        return False

    if grid[row][column] + grid[row+1][column] + grid[row+2][column] != total:
        return False
    if grid[row][column+1] + grid[row+1][column+1] + grid[row+2][column+1] != total:
        return False
    if grid[row][column+2] + grid[row+1][column+2] + grid[row+2][column+2] != total:
        return False

    # Check the diagonals
    if grid[row][column] + grid[row+1][column+1] + grid[row+2][column+2] != total:
        return False
    if grid[row][column+2] + grid[row+1][column+1] + grid[row+2][column] != total:
        return False

    return True

Big(O) Analysis

Time Complexity

O(mn) – Given an m x n grid, the algorithm iterates through all possible starting positions for a 3x3 subgrid. This results in (m-2) * (n-2) possible 3x3 subgrids to consider. For each of these subgrids, a constant amount of work is done to validate if it is a magic square, which involves checking if the numbers are 1-9 and summing rows, columns, and diagonals. Therefore, the overall time complexity is O((m-2)*(n-2)), which simplifies to O(mn) when considering the dominant terms as m and n grow large.

Space Complexity

O(1) – The provided brute force algorithm examines 3x3 squares within a larger grid without using auxiliary data structures that scale with the input grid's dimensions. It primarily uses a fixed number of variables for iteration and sum calculations within each 3x3 square. The 'contains only the numbers 1 through 9' check could use a constant-size array or set to keep track of the presence of each digit, independent of the input grid size. Therefore, the space complexity remains constant, regardless of the input grid's size (N). So the space used doesn't depend on the input size, making the space complexity O(1).

Optimal Solution

Approach

To find magic squares in a grid, we avoid brute-force checking every possible square. We focus on a clever method to quickly identify potential magic squares based on their central number and row/column sums. This reduces the number of squares we need to fully validate, significantly improving efficiency.

Here's how the algorithm would work step-by-step:

Focus on 3x3 subgrids within the larger grid.
Check if the center number of the 3x3 subgrid is 5. A magic square with digits 1-9 must have 5 in the center.
Check if all numbers from 1 to 9 are present within the 3x3 subgrid. If not, it can't be a magic square.
Verify if the sums of each row, each column, and both diagonals are equal to 15. If not, it's not a magic square.
If all the above conditions are met, count it as a magic square.
Move the 3x3 window across the grid to examine all possible 3x3 subgrids within the larger grid.
Count the total number of magic squares found.

Code Implementation

def magic_squares_in_grid(grid):
    row_length = len(grid)
    column_length = len(grid[0])
    magic_square_count = 0

    for row in range(row_length - 2):
        for column in range(column_length - 2):
            # Check if the center element is 5
            if grid[row+1][column+1] != 5:
                continue

            subgrid = []
            for i in range(3):
                for j in range(3):
                    subgrid.append(grid[row+i][column+j])

            # Check if all numbers from 1 to 9 are present
            if len(set(subgrid)) != 9 or min(subgrid) != 1 or max(subgrid) != 9:

                continue

            # Check if rows, columns, and diagonals sum to 15
            if (grid[row][column] + grid[row][column+1] + grid[row][column+2] == 15 and\
                grid[row+1][column] + grid[row+1][column+1] + grid[row+1][column+2] == 15 and\
                grid[row+2][column] + grid[row+2][column+1] + grid[row+2][column+2] == 15 and\
                grid[row][column] + grid[row+1][column] + grid[row+2][column] == 15 and\
                grid[row][column+1] + grid[row+1][column+1] + grid[row+2][column+1] == 15 and\
                grid[row][column+2] + grid[row+1][column+2] + grid[row+2][column+2] == 15 and\
                grid[row][column] + grid[row+1][column+1] + grid[row+2][column+2] == 15 and\
                grid[row][column+2] + grid[row+1][column+1] + grid[row+2][column] == 15):

                magic_square_count += 1

    return magic_square_count

Big(O) Analysis

Time Complexity

O(m*n) – Given an m x n grid, the algorithm iterates through potential 3x3 subgrids. The outer loops iterate over the rows and columns, effectively sliding the 3x3 window across the grid. For each potential 3x3 subgrid, we perform a constant amount of work: checking the center is 5, verifying the presence of numbers 1-9, and calculating row, column, and diagonal sums. Since the work inside each subgrid check is constant, the overall time complexity is determined by the number of possible 3x3 subgrids which is proportional to m*n. Therefore, the time complexity is O(m*n).

Space Complexity

O(1) – The algorithm primarily uses a few integer variables for loop indices, sums, and counting magic squares. The dominant space usage comes from checking if all numbers from 1 to 9 are present within the 3x3 subgrid, which can be implemented using a fixed-size array or set of size 9. Regardless of the grid size (N x N), the space used for these variables remains constant, leading to O(1) space complexity. No auxiliary data structures grow with the input size, so the space used is independent of N.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as no magic square can exist.
Grid dimensions less than 3x3	Return 0 since a magic square requires at least 3 rows and 3 columns.
Grid containing values outside the range [1, 9]	The isMagicSquare function should validate each cell value is within [1, 9]; if not, the square is not magic.
Grid with extremely large dimensions (performance)	The solution should avoid unnecessary computations within the sliding window approach for efficiency.
No magic squares present in the grid	The algorithm should correctly return 0 if no 3x3 subgrid satisfies the magic square property.
Multiple overlapping magic squares	The sliding window approach implicitly handles overlapping magic squares, counting each valid one.
Integer overflow when calculating sums	Use appropriate data types (e.g., int) to prevent potential overflow when summing rows, columns, and diagonals.
Grid contains only one unique value within the range [1,9]	The isMagicSquare function should return false since a magic square requires distinct values to satisfy the sum conditions.

Null or empty grid

How to Handle:

Return 0 immediately as no magic square can exist.

Grid dimensions less than 3x3

How to Handle:

Return 0 since a magic square requires at least 3 rows and 3 columns.

Grid containing values outside the range [1, 9]

How to Handle:

The isMagicSquare function should validate each cell value is within [1, 9]; if not, the square is not magic.

Grid with extremely large dimensions (performance)

How to Handle:

The solution should avoid unnecessary computations within the sliding window approach for efficiency.

No magic squares present in the grid

How to Handle:

The algorithm should correctly return 0 if no 3x3 subgrid satisfies the magic square property.

Multiple overlapping magic squares

How to Handle:

The sliding window approach implicitly handles overlapping magic squares, counting each valid one.

Integer overflow when calculating sums

How to Handle:

Use appropriate data types (e.g., int) to prevent potential overflow when summing rows, columns, and diagonals.

Grid contains only one unique value within the range [1,9]

How to Handle:

The isMagicSquare function should return false since a magic square requires distinct values to satisfy the sum conditions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the bounds on the dimensions of the grid (number of rows and columns)?
Can the values within the grid be negative, zero, or non-integer?
If no 3x3 magic square exists within the grid, what should I return (e.g., 0, -1, null)?
Are all values within a potential 3x3 magic square guaranteed to be distinct integers between 1 and 9 (inclusive)?
Is it possible for a 3x3 magic square to overlap with another? (I.e., can a row/column be part of multiple magic squares)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to consider every possible starting point for a 3x3 square inside the bigger grid.
For each starting point, we grab the 3x3 square and carefully examine its numbers.
To check if it's a magic square, we first make sure it contains only the numbers 1 through 9, and that each number appears only once.
Then, we add up the numbers in each row, each column, and both diagonals.
If all those sums are the same, then we've found a magic square, and we increase our count.
We repeat this process for every possible 3x3 square within the larger grid.
Finally, the total count of magic squares we found is our answer.

Code Implementation

def num_magic_squares_inside(grid):
    row_length = len(grid)
    column_length = len(grid[0])
    magic_square_count = 0

    for row in range(row_length - 2):
        for column in range(column_length - 2):
            # Iterate through all possible 3x3 subgrids
            if is_magic_square(grid, row, column):
                magic_square_count += 1

    return magic_square_count

def is_magic_square(grid, row, column):
    numbers = []
    for i in range(row, row + 3):
        for j in range(column, column + 3):
            numbers.append(grid[i][j])

    #Verify all digits from 1 to 9 are present
    if set(numbers) != set(range(1, 10)): 
        return False

    total = 15
    if grid[row][column] + grid[row][column+1] + grid[row][column+2] != total:
        return False
    if grid[row+1][column] + grid[row+1][column+1] + grid[row+1][column+2] != total:
        return False
    if grid[row+2][column] + grid[row+2][column+1] + grid[row+2][column+2] != total:
        return False

    if grid[row][column] + grid[row+1][column] + grid[row+2][column] != total:
        return False
    if grid[row][column+1] + grid[row+1][column+1] + grid[row+2][column+1] != total:
        return False
    if grid[row][column+2] + grid[row+1][column+2] + grid[row+2][column+2] != total:
        return False

    # Check the diagonals
    if grid[row][column] + grid[row+1][column+1] + grid[row+2][column+2] != total:
        return False
    if grid[row][column+2] + grid[row+1][column+1] + grid[row+2][column] != total:
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Focus on 3x3 subgrids within the larger grid.
Check if the center number of the 3x3 subgrid is 5. A magic square with digits 1-9 must have 5 in the center.
Check if all numbers from 1 to 9 are present within the 3x3 subgrid. If not, it can't be a magic square.
Verify if the sums of each row, each column, and both diagonals are equal to 15. If not, it's not a magic square.
If all the above conditions are met, count it as a magic square.
Move the 3x3 window across the grid to examine all possible 3x3 subgrids within the larger grid.
Count the total number of magic squares found.

Code Implementation

def magic_squares_in_grid(grid):
    row_length = len(grid)
    column_length = len(grid[0])
    magic_square_count = 0

    for row in range(row_length - 2):
        for column in range(column_length - 2):
            # Check if the center element is 5
            if grid[row+1][column+1] != 5:
                continue

            subgrid = []
            for i in range(3):
                for j in range(3):
                    subgrid.append(grid[row+i][column+j])

            # Check if all numbers from 1 to 9 are present
            if len(set(subgrid)) != 9 or min(subgrid) != 1 or max(subgrid) != 9:

                continue

            # Check if rows, columns, and diagonals sum to 15
            if (grid[row][column] + grid[row][column+1] + grid[row][column+2] == 15 and\
                grid[row+1][column] + grid[row+1][column+1] + grid[row+1][column+2] == 15 and\
                grid[row+2][column] + grid[row+2][column+1] + grid[row+2][column+2] == 15 and\
                grid[row][column] + grid[row+1][column] + grid[row+2][column] == 15 and\
                grid[row][column+1] + grid[row+1][column+1] + grid[row+2][column+1] == 15 and\
                grid[row][column+2] + grid[row+1][column+2] + grid[row+2][column+2] == 15 and\
                grid[row][column] + grid[row+1][column+1] + grid[row+2][column+2] == 15 and\
                grid[row][column+2] + grid[row+1][column+1] + grid[row+2][column] == 15):

                magic_square_count += 1

    return magic_square_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as no magic square can exist.
Grid dimensions less than 3x3	Return 0 since a magic square requires at least 3 rows and 3 columns.
Grid containing values outside the range [1, 9]	The isMagicSquare function should validate each cell value is within [1, 9]; if not, the square is not magic.
Grid with extremely large dimensions (performance)	The solution should avoid unnecessary computations within the sliding window approach for efficiency.
No magic squares present in the grid	The algorithm should correctly return 0 if no 3x3 subgrid satisfies the magic square property.
Multiple overlapping magic squares	The sliding window approach implicitly handles overlapping magic squares, counting each valid one.
Integer overflow when calculating sums	Use appropriate data types (e.g., int) to prevent potential overflow when summing rows, columns, and diagonals.
Grid contains only one unique value within the range [1,9]	The isMagicSquare function should return false since a magic square requires distinct values to satisfy the sum conditions.

Null or empty grid

How to Handle:

Return 0 immediately as no magic square can exist.

Grid dimensions less than 3x3

How to Handle:

Return 0 since a magic square requires at least 3 rows and 3 columns.

Grid containing values outside the range [1, 9]

How to Handle:

The isMagicSquare function should validate each cell value is within [1, 9]; if not, the square is not magic.

Grid with extremely large dimensions (performance)

How to Handle:

The solution should avoid unnecessary computations within the sliding window approach for efficiency.

No magic squares present in the grid

How to Handle:

The algorithm should correctly return 0 if no 3x3 subgrid satisfies the magic square property.

Multiple overlapping magic squares

How to Handle:

The sliding window approach implicitly handles overlapping magic squares, counting each valid one.

Integer overflow when calculating sums

How to Handle:

Use appropriate data types (e.g., int) to prevent potential overflow when summing rows, columns, and diagonals.

Grid contains only one unique value within the range [1,9]

How to Handle:

The isMagicSquare function should return false since a magic square requires distinct values to satisfy the sum conditions.