LeetCode 840: Magic Squares In Grid Solution
Master LeetCode problem 840 (Magic Squares In Grid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
840. Magic Squares In Grid
Problem Explanation
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.
Solution Code
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;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 840 (Magic Squares In Grid)?
This page provides optimized solutions for LeetCode problem 840 (Magic Squares In Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 840 (Magic Squares In Grid)?
The time complexity for LeetCode 840 (Magic Squares In Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 840 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 840 in Java, C++, or Python.