Find the largest Magic Square

Question

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

The question can be found here on leetcode

I first wanted to see if a naive brute force approach would pass, so I came up with the following algorithm

1. Iterate through all values of k (from min(rows,cols) of the matrix to 1)
2. For each of the k values, check if it's possible to create a magic of square of dimensions kxk by checking all possible sub matrices and return k if it's possible. This would be O(rows*cols*k^2)

So that would make the overall complexity O(k^3*rows*cols). (Please correct me if I am wrong)

I have attached my code in C++ below

class Solution {
public:
    int largestMagicSquare(vector<vector<int>>& grid) {
        int rows = grid.size(),cols = grid[0].size();
        for(int k = min(rows,cols); k >= 2; k--){ // iterate over all values of k
            for(int i = 0; i < rows-k+1; i++){
                for(int j = 0; j < cols-k+1; j++){
                    
                    int startX = i, startY = j, endX = i+k-1, endY = j+k-1;
                    int diagSum = 0, antiDiagSum = 0;
                    bool valid = true;
                    
                    // calculate sum of diag
                    for(int count = 0; count < k; count++){
                        diagSum += grid[startX][startY];
                        startX++,startY++;
                    }
                    // this is the sum that must be same across all rows, cols, diag and antidiag
                    int sum = diagSum; 
                    
                    // calculate sum of antidiag
                    for(int count = 0; count < k; count++){
                        antiDiagSum += grid[endX][endY];
                        endX--,endY--;
                    }
                    if(antiDiagSum != sum) continue;
                    
                    // calculate sum across cols
                    for(int r = i; r <=i+k-1; r++){
                        int colSum = 0;
                        for(int c = j; c <= j+k-1; c++){
                            colSum += grid[r][c];
                        }
                        if(colSum != sum){
                            valid = false;
                            break;
                        }
                    }
                    if(!valid) continue;
                    
                    // calculate sum across rows
                    for(int c = j; c <= j+k-1; c++){
                        int rowSum = 0;
                        for(int r = i; r <= i+k-1; r++){
                            rowSum += grid[r][c];
                        }
                        if(rowSum != sum){
                            valid = false;
                            break;
                        }
                    }
                    if(!valid) continue;
                    return k;
                }
            }
        }
        return 1;
    }
};

I thought I would optimize the solution once this works (Maybe binary search over the values of k). However, my code is failing for a really large test case for a matrix of dimension 50x50 after passing 74/80 test cases on Leetcode.

I tried to find out the source(s) that could be causing it to fail, but I am not really sure where the error is.

Any help would be appreciated. Thanks!
Please do let me know if further clarification about the code is needed

Answer 1

The calculation of antiDiagSum is wrong: it actually sums the values on the same diagonal as diagSum, just in reverse order. To traverse the opposite diagonal, you need to increment the Y coordinate and decrement the X coordinate (or vice versa), but your code decrements both of them.

It is probably easiest if you fix this by calculating both diagonal sums in the same loop:

for(int count = 0; count < k; count++){
    diagSum += grid[startX][startY];
    antiDiagSum += grid[endX][startY]; 
    startX++, startY++, endX--;
}