840. Magic Squares In Grid
Explanation
To solve this problem, we need to iterate through each 3 x 3 subgrid in the given grid and check if it forms a magic square. For each subgrid, we check if the sum of each row, column, and both diagonals is equal. We also need to ensure that the numbers in the subgrid are distinct and within the range of 1 to 9.
We can iterate through each cell in the grid and consider it as the top-left cell of a potential 3 x 3 magic square. Then we can check all the conditions mentioned above to determine if it is a magic square. The time complexity of this approach is O(row * col) where row and col are the number of rows and columns in the given grid.
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int count = 0;
for (int i = 0; i <= grid.length - 3; i++) {
for (int j = 0; j <= grid[0].length - 3; j++) {
if (isMagicSquare(grid, i, j)) {
count++;
}
}
}
return count;
}
private boolean isMagicSquare(int[][] grid, int row, int col) {
int[] nums = new int[16];
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 || nums[grid[i][j]] > 0) {
return false;
}
nums[grid[i][j]]++;
}
}
int sum = grid[row][col] + grid[row][col + 1] + grid[row][col + 2];
for (int i = row + 1; i < row + 3; i++) {
int currentSum = grid[i][col] + grid[i][col + 1] + grid[i][col + 2];
if (currentSum != sum) {
return false;
}
}
for (int j = col; j < col + 3; j++) {
int currentSum = grid[row][j] + grid[row + 1][j] + grid[row + 2][j];
if (currentSum != sum) {
return false;
}
}
if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != sum) {
return false;
}
if (grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != sum) {
return false;
}
return true;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.