Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/840.html

840. Magic Squares In Grid (Easy)

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 an grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).

 

Example 1:

Input: [[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:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. 0 <= grid[i][j] <= 15

Companies:
Google

Related Topics:
Array

Solution 1.

• Java
• C++
• Python

• class Solution {
      public int numMagicSquaresInside(int[][] grid) {
          int rows = grid.length, columns = grid[0].length;
          if (rows < 3 || columns < 3)
              return 0;
          int count = 0;
          int rowEnd = rows - 3, columnEnd = columns - 3;
          for (int i = 0; i <= rowEnd; i++) {
              for (int j = 0; j <= columnEnd; j++) {
                  if (isMagicSquare(grid, i, j))
                      count++;
              }
          }
          return count;
      }
  
      public boolean isMagicSquare(int[][] grid, int startRow, int startColumn) {
          if (grid[startRow + 1][startColumn + 1] != 5)
              return false;
          boolean[] exists = new boolean[16];
          exists[5] = true;
          int sumRow1 = 0, sumRow2 = 0, sumColumn1 = 0, sumColumn2 = 0;
          for (int i = 0; i < 3; i++) {
              int num1 = grid[startRow][startColumn + i];
              int num2 = grid[startRow + 2][startColumn + i];
              int num3 = grid[startRow + i][startColumn];
              int num4 = grid[startRow + i][startColumn + 2];
              exists[num1] = true;
              exists[num2] = true;
              exists[num3] = true;
              exists[num4] = true;
              sumRow1 += num1;
              sumRow2 += num2;
              sumColumn1 += num3;
              sumColumn2 += num4;
          }
          for (int i = 1; i <= 9; i++) {
              if (!exists[i])
                  return false;
          }
          return sumRow1 == 15 && sumRow2 == 15 && sumColumn1 == 15 && sumColumn2 == 15;
      }
  }
  

• // OJ: https://leetcode.com/problems/magic-squares-in-grid/
  // Time: O(MN)
  // Space: O(1)
  class Solution {
  private:
      bool isMagic(vector<vector<int>>& grid, int x, int y) {
          if (grid[x + 1][y + 1] != 5) return false;
          int cnt[9] = {0};
          for (int i = 0; i < 3; ++i) {
              int xSum = 0, ySum = 0;
              for (int j = 0; j < 3; ++j) {
                  int v = grid[x + i][y + j];
                  if (v < 1 || v > 9 || cnt[v - 1]) return false;
                  cnt[v - 1]++;
                  xSum += v;
                  ySum += grid[x + j][y + i];
              }
              if (xSum != 15 || ySum != 15) return false;
          }
          return (grid[x][y] + grid[x + 2][y + 2] == 10)
              && (grid[x][y + 2] + grid[x + 2][y] == 10);
      }
  public:
      int numMagicSquaresInside(vector<vector<int>>& grid) {
          int M = grid.size(), N = grid[0].size(), cnt = 0;
          for (int i = 0; i <= M - 3; ++i) {
              for (int j = 0; j <= N - 3; ++j) {
                  if (isMagic(grid, i, j)) ++cnt;
              }
          }
          return cnt;
      }
  };
  

• class Solution:
      def numMagicSquaresInside(self, grid):
          """
          :type grid: List[List[int]]
          :rtype: int
          """
          if len(grid) < 3 or len(grid[0]) < 3:
              return 0
          counter = 0
          for row in range(len(grid) - 2):
              for col in range(len(grid[0]) - 2):
                  sub_matrix = [[grid[row + i][col + j] for j in range(3)] for i in range(3)]
                  if self.magic_square(sub_matrix):
                      counter += 1
          return counter
  
      def magic_square(self, matrix):
          is_number_right = all(1 <= matrix[i][j] <= 9 for i in range(3) for j in range(3))
          is_row_right = all(sum(row) == 15 for row in matrix)
          is_col_right = all(sum(col) == 15 for col in [[matrix[i][j] for i in range(3)] for j in range(3)])
          is_diagonal_right = matrix[1][1] == 5 and matrix[0][0] + matrix[-1][-1] == 10 and matrix[0][-1] + matrix[-1][0] == 10
          is_repeat_right = len(set(matrix[i][j] for i in range(3) for j in range(3))) == 9
          return is_number_right and is_row_right and is_col_right and is_diagonal_right and is_repeat_right
  

All Problems

All Solutions