leetcode

0 class Solution {

1 mutable int n, m;

2

3 bool exists(const vector<vector<int>> &mat, const int threshold, const int side) const {

4 for (int i = 0; i < n - side; i++) {

5 for (int j = 0; j < m - side; j++) {

6 int crnt = mat[i + side][j + side];

7 if (i > 0) crnt -= mat[i - 1][j + side];

8 if (j > 0) crnt -= mat[i + side][j - 1];

9 if (i > 0 && j > 0) crnt += mat[i - 1][j - 1];

10 if (crnt <= threshold) return true;

11 }

12 }

13 return false;

14 }

15

16 public:

17 int maxSideLength(vector<vector<int>> &mat, const int threshold) const {

18 n = size(mat), m = size(mat[0]);

19

20 for (int i = 0, acc = 0; i < n; i++)

21 mat[i][0] = acc += mat[i][0];

22 for (int j = 0, acc = 0; j < m; j++)

23 mat[0][j] = acc += mat[0][j];

24 for (int i = 1; i < n; i++) {

25 for (int j = 1; j < m; j++) {

26 mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];

27 }

28 }

29

30 int low = 1, high = min(n, m);

31

32 while (low <= high) {

33 const int mid = low + (high - low) / 2;

34 if (exists(mat, threshold, mid - 1))

35 low = mid + 1;

36 else

37 high = mid - 1;

38 }

39

40 return high;

41 }

42 };