Magic Squares In Grid

Leetcode Problem:

• Magic Squares In Grid

Summary

• Count the number of 3x3 magic square subgrids in a given grid.

Approach

• The approach used is to iterate over the grid and for each possible 3x3 subgrid, check if it is a magic square by verifying the sums of rows, columns, and diagonals
• If all conditions are met, increment the counter.

Complexity

• O(R*C*(R*C)) where R is the number of rows and C is the number of columns in the grid.

Explain

• The solution iterates over the grid and checks each 3x3 subgrid
• For each subgrid, it checks if all numbers are distinct and within the range 1-9
• Then, it calculates the sums of rows, columns, and diagonals and checks if they are all equal
• If all conditions are met, it increments the counter
• The time complexity is O(R*C*(R*C)) due to the nested loops and calculations.

Solution Code:

class Solution {
public:
    int numMagicSquaresInside(vector>& grid) {
        int ans = 0;
        if (grid.size() < 3 || grid[0].size() < 3) return 0;
        for(int i = 0 ; i < grid.size() - 2; i++){
            for(int j = 0 ; j < grid[i].size() - 2; j++){
                int cnt = 0;
                int sum = 0;
                bool visited[10] = {false};
                for(int r =i; r < i + 3; r++){
                    for(int c = j; c < j + 3; c++){
                        if(grid[r][c] < 1 || grid[r][c] >= 10 || visited[grid[r][c]]) break;
                        cnt++;
                        visited[grid[r][c]] = true;
                    }
                }
                int sumArr[8] = {0};
                if (cnt == 9){
                    for(int k = 0 ; k < 3; k++){
                        sumArr[0] += grid[i][j+k];
                        sumArr[1] += grid[i+1][j+k];
                        sumArr[2] += grid[i+2][j+k];
                        sumArr[3] += grid[i+k][j];
                        sumArr[4] += grid[i+k][j+1];
                        sumArr[5] += grid[i+k][j+2];
                        sumArr[6] += grid[i+k][j+k];
                        sumArr[7] += grid[i+k][j+2-k];
                    }
                    bool isMagicGrid = true;
                    for(int k = 1 ; k < 8; k++){
                        if (sumArr[k] != sumArr[0]){
                            isMagicGrid = false;
                            break;
                        }
                    }
                    if (isMagicGrid){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};