leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1292.cpp (1341B)

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 };