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 <= grid.length <= 10
1 <= grid[0].length <= 10
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