# Solving Leetcode Interviews in Seconds with AI: Magic Squares In Grid


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "840" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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  

	# Explanation
	Here's a breakdown of the approach, followed by the Python code:

*   **Iterate through possible 3x3 subgrids:**  The code iterates through the input grid, checking each possible 3x3 subgrid to see if it's a magic square.
*   **Magic Square Validation:** A helper function efficiently validates if a given 3x3 grid is a magic square.  This involves checking if all numbers are within the range 1-9, are distinct, and that all rows, columns, and diagonals sum to the same value (15).
*   **Counting Valid Squares:**  The code maintains a count of the valid magic squares found.

*   **Runtime Complexity:** O(row \* col), **Storage Complexity:** O(1)

	
	# Code
	```python
	def numMagicSquaresInside(grid):
    """
    Finds the number of 3 x 3 magic square subgrids in a larger grid.

    Args:
        grid: A list of lists of integers representing the grid.

    Returns:
        The number of 3 x 3 magic square subgrids in the grid.
    """

    def is_magic_square(subgrid):
        """
        Checks if a 3 x 3 grid is a magic square.

        Args:
            subgrid: A list of lists of integers representing the 3 x 3 grid.

        Returns:
            True if the grid is a magic square, False otherwise.
        """
        nums = []
        for r in range(3):
            for c in range(3):
                nums.append(subgrid[r][c])

        if len(set(nums)) != 9:
            return False

        for num in nums:
            if num < 1 or num > 9:
                return False

        magic_constant = 15  # Expected sum for rows, columns, and diagonals

        # Check rows
        for r in range(3):
            if sum(subgrid[r]) != magic_constant:
                return False

        # Check columns
        for c in range(3):
            if subgrid[0][c] + subgrid[1][c] + subgrid[2][c] != magic_constant:
                return False

        # Check diagonals
        if subgrid[0][0] + subgrid[1][1] + subgrid[2][2] != magic_constant:
            return False
        if subgrid[0][2] + subgrid[1][1] + subgrid[2][0] != magic_constant:
            return False

        return True

    row = len(grid)
    col = len(grid[0])

    count = 0
    for r in range(row - 2):
        for c in range(col - 2):
            subgrid = [
                [grid[r][c], grid[r][c + 1], grid[r][c + 2]],
                [grid[r + 1][c], grid[r + 1][c + 1], grid[r + 1][c + 2]],
                [grid[r + 2][c], grid[r + 2][c + 1], grid[r + 2][c + 2]],
            ]
            if is_magic_square(subgrid):
                count += 1

    return count
	```