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, 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

    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