Maximum Side Length of a Square with Sum Less than or Equal to Threshold LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maxSideLength(vector<vector<int>> &mat, int threshold) {
4
    int m = mat.size();
5
    int n = mat[0].size();
6

7
    int least = min(m, n);
8

9
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
10

11
    /*
12
    create dp matrix with sum of all squares
13
    so for the following input matrix
14
     1 1 1 1
15
     1 0 0 0
16
     1 0 0 0
17
     1 0 0 0
18

19
    m = 4; n = 4; least = 4; threshold = 6
20
    you get the dp matrix to be:
21
     0 0 0 0 0
22
     0 1 2 3 4
23
     0 2 3 4 5
24
     0 3 4 5 6
25
     0 4 5 6 7
26
    */
27

28
    for (int i = 0; i < m; i++) {
29
      for (int j = 0; j < n; j++) {
30
        dp[i + 1][j + 1] = mat[i][j] + dp[i + 1][j] + dp[i][j + 1] - dp[i][j];
31
      }
32
    }
33

34
    int sum = 0;
35

36
    /*
37
    from the previous example the once we start looking from least = 4 to see if
38
    the sum is less than threshold for least = 4; sum = 7 - 0 - 0 + 0. (looking
39
    at the full 4 x 4 matrix) 7 is > threshold.. so keep looking.. for least =
40
    3; sum = 5 - 0 - 0 + 0. (looking at the 3 x 3 matrix) .. 5 < threshold..
41
    return 3.
42

43
    say if the threshold was lower e.g. threshold = 2?
44
    continuing...
45
    for least = 3; sum = 6 - 3 - 0 + 0 = 3.
46
    for least = 3; sum = 6 - 0 - 3 + 0 = 3;
47
    for least = 3; sum = 7 - 4 - 4 + 1 = 0;
48

49
    */
50

51
    for (int k = least; k > 0; k--) {
52
      for (int i = k; i < m + 1; i++) {
53
        for (int j = k; j < n + 1; j++) {
54
          sum = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k];
55
          if (sum <= threshold) {
56
            return k;
57
          }
58
        }
59
      }
60
    }
61

62
    return 0;
63
  }
64
};