Leetcode 840: Magic Squares In Grid
Given a grid of integers, the task is to find how many 3x3 magic square subgrids are present in the given grid. A 3x3 magic square is a grid that contains distinct numbers from 1 to 9, such that each row, each column, and both diagonals have the same sum. The input grid can contain numbers ranging from 0 to 15, but only numbers between 1 and 9 are valid for forming a magic square.
Problem
Approach
Steps
Complexity
Input: You are given a 2D grid of integers. The grid may contain numbers from 0 to 15. You need to identify all 3x3 subgrids that form a magic square.
Example: Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Constraints:
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15
Output: Return the count of 3x3 magic square subgrids in the given grid.
Example: Output: 1
Constraints:
• The output should be a non-negative integer representing the count of magic square subgrids.
Goal: The goal is to iterate through the grid and identify all possible 3x3 subgrids, check if they form a magic square, and count how many such squares exist.
Steps:
• Step 1: Iterate through all possible 3x3 subgrids in the given grid.
• Step 2: For each subgrid, check if it contains distinct numbers from 1 to 9.
• Step 3: Verify if the sum of each row, column, and both diagonals is the same.
• Step 4: If the subgrid forms a magic square, increment the count.
• Step 5: Return the count of magic square subgrids.
Goal: Ensure the input grid meets the specified dimensions and constraints.
Steps:
• Grid dimensions should be within the specified bounds: 1 <= row, col <= 10.
• Values in the grid should be between 0 and 15, but only values from 1 to 9 are considered for magic squares.
Assumptions:
• The grid contains integers within the specified range, but only numbers between 1 and 9 can form a valid magic square.
• The grid may contain numbers greater than 9, but they will not be considered part of the magic square.
• Input: Input: [[4, 3, 8, 4], [9, 5, 1, 9], [2, 7, 6, 2]]
• Explanation: In this grid, the subgrid containing the numbers 4, 3, 8, 9, 5, 1, 2, 7, 6 forms a valid 3x3 magic square because the sum of each row, column, and diagonal is 15.
• Input: Input: [[8]]
• Explanation: In this case, the grid is too small to contain any 3x3 subgrids, so the output is 0.
Approach: The approach involves checking each possible 3x3 subgrid in the grid, verifying if the numbers are distinct and within the valid range, and then checking if they form a magic square.
Observations:
• To solve the problem efficiently, we need to iterate through the grid and extract each possible 3x3 subgrid.
• We must check if the values are distinct and lie between 1 and 9.
• By checking the sum of rows, columns, and diagonals, we can determine whether a given subgrid is a magic square.
Steps:
• Step 1: Initialize a counter to keep track of the number of magic squares.
• Step 2: Loop through the grid and extract each possible 3x3 subgrid.
• Step 3: For each subgrid, check if the numbers are distinct and in the valid range.
• Step 4: If the subgrid forms a magic square, increment the counter.
• Step 5: Return the counter as the result.
Empty Inputs:
• If the grid is smaller than 3x3, no magic squares can exist.
Large Inputs:
• For grids near the maximum size of 10x10, ensure the solution handles the larger number of possible subgrids efficiently.
Special Values:
• Grids containing values outside the valid range (1-9) should not be considered for magic square formation.
Constraints:
• Ensure the grid dimensions are within the specified limits, and handle values greater than 9 appropriately.
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int res = 0;
for(int i = 0; i < m -2; i++)
for(int j = 0; j < n -2; j++)
if(isMagic(grid, i, j))
res++;
return res;
}
bool isMagic(vector<vector<int>> &grid, int row, int col) {
int record[10] = {0};
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 + 2][col] + grid[row + 1][col + 1] + grid[row][col + 2];
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;
}
1 : Function
int numMagicSquaresInside(vector<vector<int>>& grid) {
The main function that counts the number of magic squares inside the given grid. It iterates through potential 3x3 subgrids.
2 : Variable Declaration
int m = grid.size(), n = grid[0].size();
Declare the dimensions of the grid (m rows and n columns).
3 : Variable Initialization
int res = 0;
Initialize the result variable to count the number of magic squares.
4 : Loop
for(int i = 0; i < m - 2; i++)
Outer loop to iterate through all possible starting rows for 3x3 subgrids.
5 : Loop
for(int j = 0; j < n - 2; j++)
Inner loop to iterate through all possible starting columns for 3x3 subgrids.
6 : Conditional
if(isMagic(grid, i, j))
Check if the current 3x3 subgrid starting at (i, j) is a magic square.
7 : Increment
res++;
If the subgrid is a magic square, increment the result.
8 : Return
return res;
Return the total count of magic squares.
9 : Function
bool isMagic(vector<vector<int>> &grid, int row, int col) {
Helper function to check if a 3x3 subgrid starting at (row, col) is a magic square.
10 : Array Initialization
int record[10] = {0};
Initialize an array to track numbers that have been seen in the 3x3 subgrid.
11 : Loop
for(int i = row; i < row + 3; i++)
Loop through the rows of the 3x3 subgrid.
12 : Loop
for(int j = col; j < col + 3; j++) {
Loop through the columns of the 3x3 subgrid.
13 : Conditional
if(grid[i][j] < 1 || grid[i][j] > 9 || record[grid[i][j]] > 0)
Check if the current number is out of the valid range (1 to 9) or has been seen before.
14 : Return
return false;
Return false if the current subgrid is invalid.
15 : Update
record[grid[i][j]] = 1;
Mark the current number as seen.
16 : Sum Calculation
int sum1 = grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2];
Calculate the sum of the main diagonal of the 3x3 subgrid.
17 : Sum Calculation
int sum2 = grid[row + 2][col] + grid[row + 1][col + 1] + grid[row][col + 2];
Calculate the sum of the anti-diagonal of the 3x3 subgrid.
18 : Conditional
if(sum1 != sum2) return false;
If the diagonal sums are not equal, return false.
19 : Loop
for(int i = 0; i < 3; i++) {
Loop through the rows and columns to check if all rows and columns sum to the same value.
20 : Conditional
if(grid[row+i][col] + grid[row+i][col+1]+ grid[row+i][col+2] != sum1)
Check if the sum of each row is equal to the diagonal sum.
21 : Return
return false;
Return false if a row sum does not match the expected sum.
22 : Conditional
if(grid[row][col+i] + grid[row+1][col+i]+ grid[row+2][col+i] != sum1)
Check if the sum of each column is equal to the diagonal sum.
23 : Return
return false;
Return false if a column sum does not match the expected sum.
24 : Return
return true;
Return true if the subgrid is a magic square.
Best Case: O(row * col)
Average Case: O(row * col)
Worst Case: O(row * col)
Description: The time complexity is proportional to the number of subgrids that need to be checked, which is O(row * col).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, O(1), since we are using a fixed amount of additional space to store intermediate results.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus