Largest Magic Square LeetCode solution in Java

1
class Solution {
2
  public int largestMagicSquare(int[][] grid) {
3
    int m = grid.length;
4
    int n = grid[0].length;
5
    // every row prefix sum
6
    int[][] rowPrefix = new int[m][n];
7
    for (int i = 0; i < m; i++) {
8
      rowPrefix[i][0] = grid[i][0];
9
      for (int j = 1; j < n; j++) {
10
        rowPrefix[i][j] = rowPrefix[i][j - 1] + grid[i][j];
11
      }
12
    }
13

14
    // every column prefix sum
15
    int[][] columnPrefix = new int[m][n];
16
    for (int i = 0; i < n; i++) {
17
      columnPrefix[0][i] = grid[0][i];
18
      for (int j = 1; j < m; j++) {
19
        columnPrefix[j][i] = columnPrefix[j - 1][i] + grid[j][i];
20
      }
21
    }
22

23
    int result = 1;
24
    for (int i = 0; i < m; i++) {
25
      for (int j = 0; j < n; j++) {
26
        // length of square
27
        int l = Math.min(m - i, n - j);
28
        // only check square's length is better than previous result
29
        for (int k = l; k > result; k--) {
30
          if (magic(i, j, k, grid, rowPrefix, columnPrefix)) {
31
            result = k;
32
            break;
33
          }
34
        }
35
      }
36
    }
37
    return result;
38
  }
39

40
  private boolean magic(
41
      int i, int j, int l, int[][] grid, int[][] rowPrefix, int[][] columnPrefix) {
42
    // check every row
43
    int target = rowPrefix[i][j + l - 1] - rowPrefix[i][j] + grid[i][j];
44
    for (int k = 0; k < l; k++) {
45
      if (rowPrefix[i + k][j + l - 1] - rowPrefix[i + k][j] + grid[i + k][j] != target) {
46
        return false;
47
      }
48
    }
49

50
    // check every column
51
    for (int k = 0; k < l; k++) {
52
      if (columnPrefix[i + l - 1][j + k] - columnPrefix[i][j + k] + grid[i][j + k] != target) {
53
        return false;
54
      }
55
    }
56

57
    // check both diagonal
58
    int diagonal = 0;
59
    // \
60
    // \
61
    for (int k = 0; k < l; k++) {
62
      diagonal += grid[i + k][j + k];
63
    }
64

65
    if (diagonal != target) {
66
      return false;
67
    }
68

69
    // /
70
    // /
71
    for (int k = 0; k < l; k++) {
72
      diagonal -= grid[i + l - 1 - k][j + k];
73
    }
74

75
    return diagonal == 0;
76
  }
77
}