leetcode

commit 8c8e75e017cc93875a54dd9270117bd82a08d66b
parent 00ec8e88510c3911d62c9f69f3c14ef1a035d758
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 29 Jun 2024 21:22:31 +0200

1 Random Problem

Diffstat:
A
Problems/1139.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/1139.cpp b/Problems/1139.cpp
@@ -0,0 +1,28 @@
+class Solution {
+  public:
+    int largest1BorderedSquare(vector<vector<int>> &grid) {
+        static int top[101][101], left[101][101];
+        const int n = size(grid), m = size(grid[0]);
+
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                left[i][j] = grid[i - 1][j - 1] ? left[i][j - 1] + 1 : 0;
+                top[i][j] = grid[i - 1][j - 1] ? top[i - 1][j] + 1 : 0;
+            }
+        }
+
+        for (int s = min(m, n); s > 0; s--) {
+            for (int i = 0; i <= n - s; i++) {
+                for (int j = 0; j <= m - s; j++) {
+                    if (top[i + s][j + 1] < s) continue;
+                    if (top[i + s][j + s] < s) continue;
+                    if (left[i + 1][j + s] < s) continue;
+                    if (left[i + s][j + s] < s) continue;
+                    return s * s;
+                }
+            }
+        }
+
+        return 0;
+    }
+};
diff --git a/README.md b/README.md
@@ -681,6 +681,7 @@ for solving problems.
 |  1130  |   Medium   | [Minimum Cost Tree From Leaf Values](Problems/1130.cpp)                                            |
 |  1137  |    Easy    | [N-th Tribonacci Number](Problems/1137.cpp)                                                        |
 |  1138  |   Medium   | [Alphabet Board Path](Problems/1138.cpp)                                                           |
+|  1139  |   Medium   | [Largest 1-Bordered Square](Problems/1139.cpp)                                                     |
 |  1140  |   Medium   | [Stone Game II](Problems/1140.cpp)                                                                 |
 |  1141  |    Easy    | [User Activity for the Past 30 Days I](Problems/1141.cpp)                                          |
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                    |