leetcode

commit 856dbf1d7a1677c7da3c92ef9ee6722a04ae6c7a
parent 81420085b4cc32b8aed587a69fda849214690fde
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun,  8 Mar 2026 21:39:35 -0600

3129. find all possible stable binary arrays 1

Diffstat:
A
find_stable_binary_arr1.c
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
find_stable_binary_arr1.py
 | 
38
++++++++++++++++++++++++++++++++++++++

2 files changed, 99 insertions(+), 0 deletions(-)
diff --git a/find_stable_binary_arr1.c b/find_stable_binary_arr1.c
@@ -0,0 +1,61 @@
+// 3129. Find All Possible Stable Binary Arrays I
+#include "leetcode.h"
+
+/*
+ * you are given 3 positive integers 'zero', 'one', and 'limit'. a binary array
+ * 'arr' is called stable if the number of occurences of 0 in 'arr' is exactly
+ * 0, the number of occurences of 1 in 'arr' is exactly 'one', and each subarray
+ * of 'arr' with a size greater than 'limit' must contain both 0 and 1. return
+ * the total number of stable binary arrays. since the answer may be very large,
+ * return it modulo 10^9 + 7.
+ */
+
+int numberOfStableArrays(int zero, int one, int limit) {
+  static int mod = 10e9 + 7;
+  long long ***dp = (long long ***)malloc((zero + 1) * sizeof(long long));
+  for (int i = 0; i < zero + 1; i++) {
+    dp[i] = (long long **)malloc((one + 1) * sizeof(long long));
+    for (int j = 0; j < one + 1; j++)
+      dp[i][j] = (long long *)calloc(2, sizeof(long long));
+  }
+  for (int i = 0; i < zero + 1; i++)
+    for (int i = 0; i <= (zero < limit ? zero : limit); ++i)
+      dp[i][0][0] = 1;
+  for (int j = 0; j <= (one < limit ? one : limit); ++j)
+    dp[0][j][1] = 1;
+  for (int i = 1; i <= zero; ++i)
+    for (int j = 1; j <= one; ++j) {
+      if (i > limit)
+        dp[i][j][0] =
+            dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
+      else
+        dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
+      dp[i][j][0] = (dp[i][j][0] % mod + mod) % mod;
+      if (j > limit)
+        dp[i][j][1] =
+            dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
+      else
+        dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
+      dp[i][j][1] = (dp[i][j][1] % mod + mod) % mod;
+    }
+  int ans = (dp[zero][one][0] + dp[zero][one][1]) % mod;
+  for (int i = 0; i < zero + 1; i++) {
+    for (int j = 0; j < one + 1; j++)
+      free(dp[i][j]);
+    free(dp[i]);
+  }
+  free(dp);
+  return ans;
+}
+
+int main() {
+  int r1 = numberOfStableArrays(1, 1, 2);
+  int r2 = numberOfStableArrays(1, 2, 1);
+  int r3 = numberOfStableArrays(3, 3, 2);
+  printf("%d\n", r1); // expect: 2
+  assert(r1 == 2);
+  printf("%d\n", r2); // expect: 1
+  assert(r2 == 1);
+  printf("%d\n", r3); // expect: 14
+  assert(r3 == 14);
+}
diff --git a/find_stable_binary_arr1.py b/find_stable_binary_arr1.py
@@ -0,0 +1,38 @@
+# 3129. Find All Possible Stable Binary Arrays I
+
+"""
+you are given 3 positive integers 'zero', 'one', and 'limit'. a binary array
+'arr' is called stable if the number of occurences of 0 in 'arr' is exactly
+0, the number of occurences of 1 in 'arr' is exactly 'one', and each subarray
+of 'arr' with a size greater than 'limit' must contain both 0 and 1. return
+the total number of stable binary arrays. since the answer may be very large,
+return it modulo 10^9 + 7.
+"""
+
+
+class Solution:
+    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
+        mod = 10**9 + 7
+
+        dp0 = [[0] * (one + 1) for _ in range(zero + 1)]
+        dp1 = [[0] * (one + 1) for _ in range(zero + 1)]
+        for i in range(1, min(zero, limit) + 1):
+            dp0[i][0] = 1
+        for j in range(1, min(one, limit) + 1):
+            dp1[0][j] = 1
+        for i in range(1, zero + 1):
+            for j in range(1, one + 1):
+                dp0[i][j] = (
+                    sum(dp1[i - k][j] for k in range(1, min(limit, i) + 1)) % mod
+                )
+                dp1[i][j] = (
+                    sum(dp0[i][j - k] for k in range(1, min(limit, j) + 1)) % mod
+                )
+        return (dp0[zero][one] + dp1[zero][one]) % mod
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.numberOfStableArrays(zero=1, one=1, limit=2))
+    print(obj.numberOfStableArrays(zero=1, one=2, limit=1))
+    print(obj.numberOfStableArrays(zero=3, one=3, limit=2))