Largest Magic Square LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isValid(int r1, int r2, int c1, int c2, vector<vector<int>> &grid, vector<vector<int>> &rg,
4
               vector<vector<int>> &cg, int checkSum) {
5
    // Checking all row sums between top and bottom row
6
    for (int i = r1 + 1; i < r2; i++) {
7
      int sum = rg[i][c2];
8
      if (c1 > 0) sum -= rg[i][c1 - 1];
9
      if (sum != checkSum) return false;
10
    }
11
    // Checking all columns between left and right column
12
    for (int j = c1 + 1; j < c2; j++) {
13
      int sum = cg[r2][j];
14
      if (r1 > 0) sum -= cg[r1 - 1][j];
15
      if (sum != checkSum) return false;
16
    }
17
    int sum = 0;
18
    // right diagonal
19
    for (int i = r1, j = c1; i <= r2 && j <= c2; i++, j++) {
20
      sum += grid[i][j];
21
    }
22
    if (sum != checkSum) return false;
23
    sum = 0;
24
    // left diagonal
25
    for (int i = r1, j = c2; i <= r2 && j >= c1; i++, j--) {
26
      sum += grid[i][j];
27
    }
28
    if (sum != checkSum) return false;
29
    return true;
30
  }
31
  int largestMagicSquare(vector<vector<int>> &grid) {
32
    int m = grid.size(), n = grid[0].size();
33
    vector<vector<int>> rg, cg;
34
    rg = grid;
35
    cg = grid;
36
    // Generating row prefix sum matrix
37
    for (int i = 0; i < m; i++) {
38
      for (int j = 1; j < n; j++) {
39
        rg[i][j] += rg[i][j - 1];
40
      }
41
    }
42
    // Generating column prefix sum matrix
43
    for (int j = 0; j < n; j++) {
44
      for (int i = 1; i < m; i++) {
45
        cg[i][j] += cg[i - 1][j];
46
      }
47
    }
48
    int ans = 1;
49
    // For each cell in the loop, we find the larget magic square with cell
50
    // {i,j} at the top left corner.
51
    for (int i = 0; i < m; i++) {
52
      for (int j = 0; j < n; j++) {
53
        if (m - i <= ans)
54
          return ans; // The largest square with it's top row as i will have at
55
                      // max a dimension = m-i, and in case are answer is
56
                      // already >= this dimension, we can simply return our
57
                      // answer
58
        // Pruning step -->
59
        // We only need to consider squares whose sizes our greater than our
60
        // current answer, so we prune our search by starting from squares
61
        // having side-lengths greater than ans.
62
        int r = i + ans;
63
        int c = j + ans;
64
        while (r < m && c < n) {
65
          // For a square having it's 4 corners defined by {i,j,r,c}, we
66
          // calculate the sum of all these 4 sides, and call our isValid
67
          // function in case these sums are equal
68
          int rsum1 = j > 0 ? rg[i][c] - rg[i][j - 1] : rg[i][c]; // top row sum
69
          int csum1 = i > 0 ? cg[r][j] - cg[i - 1][j] : cg[r][j]; // left column sum
70
          int rsum2 = j > 0 ? rg[r][c] - rg[r][j - 1] : rg[r][c]; // bottom row sum
71
          int csum2 = i > 0 ? cg[r][c] - cg[i - 1][c] : cg[r][c]; // right column sum
72
          if (rsum1 == csum2 && rsum2 == csum2 && isValid(i, r, j, c, grid, rg, cg, rsum1)) {
73
            ans = max(ans, r - i + 1);
74
          }
75
          r++;
76
          c++;
77
        }
78
      }
79
    }
80
    return ans;
81
  }
82
};