Massive Algorithms: 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 <= grid.length <= 10
1 <= grid[0].length <= 10
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);
        set.add(x1);
        set.add(x2);
        set.add(x3);
        set.add(x4);
        
        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);
        set.add(x1);
        set.add(x2);
        set.add(x3);
        set.add(x4);
        
        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;
    }

LeetCode 840 - Magic Squares In Grid

Labels

Popular Posts