Skip to content

840. Magic Squares In Grid 👎

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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