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.

  • 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