leetcode

commit 92313963434f48afcb16fb389e61537eeeaf3588
parent ccdf347047f64d09dcb3aa68f08b4a3d68295480
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  9 Apr 2024 13:24:33 +0200

1 Random Problem

Diffstat:
A
Problems/1292.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 44 insertions(+), 0 deletions(-)
diff --git a/Problems/1292.cpp b/Problems/1292.cpp
@@ -0,0 +1,43 @@
+class Solution {
+    mutable int n, m;
+
+    bool exists(const vector<vector<int>> &mat, const int threshold, const int side) const {
+        for (int i = 0; i < n - side; i++) {
+            for (int j = 0; j < m - side; j++) {
+                int crnt = mat[i + side][j + side];
+                if (i > 0) crnt -= mat[i - 1][j + side];
+                if (j > 0) crnt -= mat[i + side][j - 1];
+                if (i > 0 && j > 0) crnt += mat[i - 1][j - 1];
+                if (crnt <= threshold) return true;
+            }
+        }
+        return false;
+    }
+
+  public:
+    int maxSideLength(vector<vector<int>> &mat, const int threshold) const {
+        n = size(mat), m = size(mat[0]);
+
+        for (int i = 0, acc = 0; i < n; i++)
+            mat[i][0] = acc += mat[i][0];
+        for (int j = 0, acc = 0; j < m; j++)
+            mat[0][j] = acc += mat[0][j];
+        for (int i = 1; i < n; i++) {
+            for (int j = 1; j < m; j++) {
+                mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
+            }
+        }
+
+        int low = 1, high = min(n, m);
+
+        while (low <= high) {
+            const int mid = low + (high - low) / 2;
+            if (exists(mat, threshold, mid - 1))
+                low = mid + 1;
+            else
+                high = mid - 1;
+        }
+
+        return high;
+    }
+};
diff --git a/README.md b/README.md
@@ -705,6 +705,7 @@ for solving problems.
 |  1288  |   Medium   | [Remove Covered Intervals](Problems/1288.cpp)                                                      |
 |  1290  |    Easy    | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp)                             |
 |  1291  |   Medium   | [Sequential Digits](Problems/1291.cpp)                                                             |
+|  1292  |   Medium   | [Maximum Side Length of a Square with Sum Less than or Equal to Threshold](Problems/1292.cpp)      |
 |  1296  |   Medium   | [Divide Array in Sets of K Consecutive Numbers](Problems/1296.cpp)                                 |
 |  1302  |   Medium   | [Deepest Leaves Sum](Problems/1302.cpp)                                                            |
 |  1305  |   Medium   | [All Elements in Two Binary Search Trees](Problems/1305.cpp)                                       |