## Thursday, June 7, 2018

### LeetCode 840 - Magic Squares In Grid

https://leetcode.com/problems/magic-squares-in-grid/description/
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`
https://leetcode.com/problems/magic-squares-in-grid/discuss/135574/Java-A-little-more-elegant-solution
I did a little math first:
There are 8 ways of having 3 distinct numbers from 1-9 to sum up to 15
``````15 = 9+5+1
= 9+4+2
= 8+6+1
= 8+5+2
= 8+4+3
= 7+6+2
= 7+5+3
= 6+5+4
``````
Note that 5 is used four times so it must be the center of magic square; 1/3/7/9 are used twice so they must be on the side, while 2/4/6/8 are used three times so they must be on the corner.
``````    public int numMagicSquaresInside(int[][] grid) {
if (grid == null || grid.length < 3 || grid[0].length < 3) {
return 0;
}

int num = 0;
for (int i = 1; i < grid.length - 1; i++) {
for (int j = 1; j < grid[0].length - 1; j++) {
if (grid[i][j] == 5
&& numsOnSideAreMagic(grid[i-1][j], grid[i+1][j], grid[i][j-1], grid[i][j+1])
&& numsOnCornerAreMagic(grid[i-1][j-1], grid[i-1][j+1], grid[i+1][j-1], grid[i+1][j+1])) {
num++;
}
}
}
return num;
}

private boolean numsOnSideAreMagic(int x1, int x2, int x3, int x4) {
Set<Integer> set = new HashSet<Integer>(4);

if (set.size() == 4 && set.contains(1) && set.contains(3) && set.contains(7) && set.contains(9)) {
return true;
}
return false;
}

private boolean numsOnCornerAreMagic(int x1, int x2, int x3, int x4) {
Set<Integer> set = new HashSet<Integer>(4);

if (set.size() == 4 && set.contains(2) && set.contains(4) && set.contains(6) && set.contains(8)) {
return true;
}
return false;
}
``````

public int numMagicSquaresInside(int[][] grid) {
int R = grid.length, C = grid[0].length;
int ans = 0;
for (int r = 0; r < R-2; ++r)
for (int c = 0; c < C-2; ++c) {
if (magic(grid[r][c], grid[r][c+1], grid[r][c+2],
grid[r+1][c], grid[r+1][c+1], grid[r+1][c+2],
grid[r+2][c], grid[r+2][c+1], grid[r+2][c+2]))
ans++;
}

return ans;
}

public boolean magic(int... vals) { //\\
int[] count = new int[16];
for (int v: vals) count[v]++;
for (int v = 1; v <= 9; ++v)
if (count[v] != 1)
return false;

return (vals[0] + vals[1] + vals[2] == 15 &&
vals[3] + vals[4] + vals[5] == 15 &&
vals[6] + vals[7] + vals[8] == 15 &&
vals[0] + vals[3] + vals[6] == 15 &&
vals[1] + vals[4] + vals[7] == 15 &&
vals[2] + vals[5] + vals[8] == 15 &&
vals[0] + vals[4] + vals[8] == 15 &&
vals[2] + vals[4] + vals[6] == 15);
}
https://leetcode.com/problems/magic-squares-in-grid/discuss/133861/Straightforward-Java-Solution
``````class Solution {
public int numMagicSquaresInside(int[][] grid) {
int m = grid.length, n = grid[0].length, result = 0;
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n - 2; j++) {
if (isMagic(grid, i, j)) {
result++;
}
}
}
return result;
}
private boolean isMagic(int[][] grid, int row, int col) {
int[] record = new int[10];
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (grid[i][j] < 1 || grid[i][j] > 9 || record[grid[i][j]] > 0) {
return false;
}
record[grid[i][j]] = 1;
}
}
int sum1 = grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2];
int sum2 = grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col];
if (sum1 != sum2) {
return false;
}
for (int i = 0; i < 3; i++) {
if (grid[row + i][col] + grid[row + i][col + 1] + grid[row + i][col + 2] != sum1) {
return false;
}
if (grid[row][col + i] + grid[row + 1][col + i] + grid[row + 2][col + i] != sum1) {
return false;
}
}
return true;
}
}``````
https://leetcode.com/problems/magic-squares-in-grid/discuss/133938/Java-8-ms-Straightforward-and-Ugly-Solution
``````public int numMagicSquaresInside(int[][] grid) {
int cnt=0;
for(int i=0;i<=grid.length-3;i++)
for(int j=0;j<=grid[0].length-3;j++)
if(helper(i,j,grid)) cnt++;

return cnt;
}

private boolean helper(int x,int y,int[][] grid){
if(grid[x+1][y+1]!=5) return false;

int[] valid=new int[16];

for(int i=x;i<=x+2;i++)
for(int j=y;j<=y+2;j++)
valid[grid[i][j]]++;

for (int v = 1; v <= 9; v++)
if (valid[v] != 1) return false;

if((grid[x][y]+grid[x][y+1]+grid[x][y+2])!=15)         return false;
if((grid[x][y]+grid[x+1][y+1]+grid[x+2][y+2])!=15)     return false;
if((grid[x][y]+grid[x+1][y]+grid[x+2][y])!=15)         return false;
if((grid[x+2][y]+grid[x+2][y+1]+grid[x+2][y+2])!=15)   return false;
if((grid[x][y+2]+grid[x+1][y+2]+grid[x+2][y+2])!=15)   return false;
if((grid[x][y+2]+grid[x+1][y+1]+grid[x+2][y])!=15)     return false;
return true;
}``````