840. Magic Squares In Grid LeetCode Solution

In this guide, you will get 840. Magic Squares In Grid LeetCode Solution with the best time and space complexity. The solution to Magic Squares In Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Magic Squares In Grid solution in C++
Magic Squares In Grid solution in Java
Magic Squares In Grid solution in Python
Additional Resources

840. Magic Squares In Grid LeetCode Solution image

Problem Statement of Magic Squares In Grid

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(1)

840. Magic Squares In Grid LeetCode Solution in C++

class Solution {
 public:
  int numMagicSquaresInside(vector<vector<int>>& grid) {
    int ans = 0;

    for (int i = 0; i + 2 < grid.size(); ++i)
      for (int j = 0; j + 2 < grid[0].size(); ++j)
        if (grid[i][j] % 2 == 0 && grid[i + 1][j + 1] == 5)
          ans += isMagic(grid, i, j);

    return ans;
  }

 private:
  int isMagic(const vector<vector<int>>& grid, int i, int j) {
    string s;

    for (const int num : {0, 1, 2, 5, 8, 7, 6, 3})
      s += to_string(grid[i + num / 3][j + num % 3]);

    return string("4381672943816729").find(s) != string::npos ||
           string("9276183492761834").find(s) != string::npos;
  }
};
/* code provided by PROGIEZ */

840. Magic Squares In Grid LeetCode Solution in Java

class Solution {
  public int numMagicSquaresInside(int[][] grid) {
    int ans = 0;

    for (int i = 0; i + 2 < grid.length; ++i)
      for (int j = 0; j + 2 < grid[0].length; ++j)
        if (grid[i][j] % 2 == 0 && grid[i + 1][j + 1] == 5)
          if (isMagic(grid, i, j))
            ++ans;

    return ans;
  }

  private boolean isMagic(int[][] grid, int i, int j) {
    String s = new String("");

    for (final int num : new int[] {0, 1, 2, 5, 8, 7, 6, 3})
      s += Integer.toString(grid[i + num / 3][j + num % 3]);

    return                                            //
        new String("4381672943816729").contains(s) || //
        new String("9276183492761834").contains(s);
  }
}
// code provided by PROGIEZ

840. Magic Squares In Grid LeetCode Solution in Python

class Solution:
  def numMagicSquaresInside(self, grid: list[list[int]]) -> int:
    def isMagic(i: int, j: int) -> int:
      s = "".join(str(grid[i + num // 3][j + num % 3])
                  for num in [0, 1, 2, 5, 8, 7, 6, 3])
      return s in "43816729" * 2 or s in "43816729"[::-1] * 2

    ans = 0

    for i in range(len(grid) - 2):
      for j in range(len(grid[0]) - 2):
        if grid[i][j] % 2 == 0 and grid[i + 1][j + 1] == 5:
          ans += isMagic(i, j)

    return ans
 # code by PROGIEZ