840. Magic Squares In Grid

[mah-shamim]

Topics: Array, Hash Table, Math, Matrix

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

[mah-shamim]

We need to count how many 3x3 contiguous subgrids in the given grid form a magic square. A magic square is a 3x3 grid where all rows, columns, and both diagonals sum to the same value, and it contains the distinct numbers from 1 to 9.

To solve this problem, we can follow these steps:

1. Check if a Subgrid is Magic:

   • The subgrid must contain all distinct numbers from 1 to 9.
   • The sum of each row, column, and diagonal should be 15.

2. Iterate through the Grid:

   • Since we need to check 3x3 subgrids, we will iterate from 0 to row-2 for rows and from 0 to col-2 for columns.
   • For each top-left corner of the 3x3 subgrid, extract the subgrid and check if it's a magic square.

Let's implement this solution in PHP: 840. Magic Squares In Grid

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function isMagic($grid, $r, $c) {
    // Extract the 3x3 grid
    $nums = [
        $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]
    ];
    
    // Check for distinct numbers from 1 to 9
    $set = array_fill(1, 9, 0);
    foreach ($nums as $num) {
        if ($num < 1 || $num > 9 || $set[$num] == 1) {
            return false;
        }
        $set[$num] = 1;
    }
    
    // Check the sums
    return (
        $grid[$r][$c] + $grid[$r][$c+1] + $grid[$r][$c+2] == 15 &&
        $grid[$r+1][$c] + $grid[$r+1][$c+1] + $grid[$r+1][$c+2] == 15 &&
        $grid[$r+2][$c] + $grid[$r+2][$c+1] + $grid[$r+2][$c+2] == 15 &&
        $grid[$r][$c] + $grid[$r+1][$c] + $grid[$r+2][$c] == 15 &&
        $grid[$r][$c+1] + $grid[$r+1][$c+1] + $grid[$r+2][$c+1] == 15 &&
        $grid[$r][$c+2] + $grid[$r+1][$c+2] + $grid[$r+2][$c+2] == 15 &&
        $grid[$r][$c] + $grid[$r+1][$c+1] + $grid[$r+2][$c+2] == 15 &&
        $grid[$r][$c+2] + $grid[$r+1][$c+1] + $grid[$r+2][$c] == 15
    );
}

/**
 * @param $grid
 * @param $r
 * @param $c
 * @return bool
 */
function numMagicSquaresInside($grid) {
    $rows = count($grid);
    $cols = count($grid[0]);
    $count = 0;
    
    for ($i = 0; $i <= $rows - 3; $i++) {
        for ($j = 0; $j <= $cols - 3; $j++) {
            if (isMagic($grid, $i, $j)) {
                $count++;
            }
        }
    }
    
    return $count;
}

// Example usage:
$grid1 = [
    [4, 3, 8, 4],
    [9, 5, 1, 9],
    [2, 7, 6, 2]
];

echo numMagicSquaresInside($grid1); // Output: 1

$grid2 = [
    [18]
];

echo numMagicSquaresInside($grid2); // Output: 0
?>

Explanation:

1. isMagic function:

   • Extracts the 3x3 subgrid.
   • Checks if all numbers are distinct and between 1 to 9.
   • Verifies that the sums of the rows, columns, and diagonals are all 15.

2. numMagicSquaresInside function:

   • Iterates over all possible 3x3 subgrids in the given grid.
   • Counts how many of those subgrids are magic squares.

This code works efficiently within the constraints, counting all 3x3 magic square subgrids in the given grid.

[basharul-siddike]

Thanks for solving the problem of "Magic Squares In Grid"

[mah-shamim]

Thanks