DEV Community

Cover image for 840. Magic Squares In Grid
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

840. Magic Squares In Grid

840. Magic Squares In Grid

Medium

Topics: Array, Hash Table, Math, Matrix

A 3 x 3 magic square is a3 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:

magic_main

  • 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:

magic_valid

while this one is not:

magic_invalid

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

Solution:

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
// 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
?>
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Billboard image

Synthetic monitoring. Built for developers.

Join Vercel, Render, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay