Largest 1-Bordered Square LeetCode solution in C++

1
class Solution {
2
 public:
3
  int largest1BorderedSquare(vector<vector<int>> &g) {
4
    int n = g.size();
5
    int m = g[0].size();
6
    int ver[n][m]; // to store lenght of continuous 1's vertically
7
    int hor[n][m]; // to store lenght of continuous 1's horizontally
8

9
    // fill vertical table
10
    for (int i = n - 1; i >= 0; i--) {
11
      for (int j = 0; j < m; j++) {
12
        if (g[i][j] == 1) {
13
          if (i == n - 1)
14
            ver[i][j] = 1;
15
          else
16
            ver[i][j] = ver[i + 1][j] + 1;
17
        } else
18
          ver[i][j] = 0;
19
      }
20
    }
21

22
    // fill horizontal table
23
    for (int i = n - 1; i >= 0; i--) {
24
      for (int j = m - 1; j >= 0; j--) {
25
        if (g[i][j] == 1) {
26
          if (j == m - 1)
27
            hor[i][j] = 1;
28
          else
29
            hor[i][j] = hor[i][j + 1] + 1;
30
        } else
31
          hor[i][j] = 0;
32
      }
33
    }
34

35
    // Iterate through the all i and j and find best solution
36
    int ans = 0;
37
    for (int i = 0; i < n; i++) {
38
      for (int j = 0; j < m; j++) {
39
        if (!g[i][j]) continue;
40
        int temp = 1;
41
        int k = min(hor[i][j], ver[i][j]);
42
        for (int p = 1; p < k; p++) {
43
          int mn = min(hor[i + p][j], ver[i][j + p]);
44
          if (mn >= p + 1) temp = p + 1;
45
        }
46
        ans = max(ans, temp);
47
      }
48
    }
49
    ans *= ans;
50
    return ans;
51
  }
52
};