LeetCode [840] Magic Squares In Grid

 840. Magic Squares In Grid

Medium

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?  (Each subgrid is contiguous).

 

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

Example 3:

Input: grid = [[4,4],[3,3]]
Output: 0

Example 4:

Input: grid = [[4,7,8],[9,5,1],[2,3,6]]
Output: 0

 

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { boolean valid(int[][] grid, int a, int b){ Set<Integer> set = new HashSet<>(); for(int i=a-2; i<=a; ++i){ for(int j=b-2; j<=b; ++j){ if(grid[i][j]<1 || grid[i][j]>9) return false; set.add(grid[i][j]); } } return set.size()==9; } public int numMagicSquaresInside(int[][] grid) { int m = grid.length; if (m == 0) return 0; int n = grid[0].length; if (n == 0) return 0; int count = 0; for (int i = 2; i < m; i++) { for (int j = 2; j < n; j++) { if(!valid(grid, i, j)) continue; int s = grid[i - 2][j - 2] + grid[i - 2][j - 1] + grid[i - 2][j]; if (grid[i - 1][j - 2] + grid[i - 1][j - 1] + grid[i - 1][j] != s) continue; if (grid[i][j - 2] + grid[i][j - 1] + grid[i][j] != s) continue; if (grid[i - 2][j - 2] + grid[i - 1][j - 2] + grid[i][j - 2] != s) continue; if (grid[i - 2][j - 1] + grid[i - 1][j - 1] + grid[i][j - 1] != s) continue; if (grid[i - 2][j] + grid[i - 1][j] + grid[i][j] != s) continue; if (grid[i - 2][j - 2] + grid[i - 1][j - 1] + grid[i][j] != s) continue; if (grid[i - 2][j] + grid[i - 1][j - 1] + grid[i][j - 2] != s) continue; count++; } } return count; } }