leetcode

commit d05edef340c99714a5696b9eb58df1775b73a782
parent 8c511efa9fb6e02856033dc22bf938a1a5830025
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 23 Jun 2026 11:08:15 -0600

3699. number of zigzag arrays 1

Diffstat:
A
num_zigzag_arrays1.c
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
num_zigzag_arrays1.py
 | 
28
++++++++++++++++++++++++++++

2 files changed, 81 insertions(+), 0 deletions(-)
diff --git a/num_zigzag_arrays1.c b/num_zigzag_arrays1.c
@@ -0,0 +1,53 @@
+// 3699. Number of ZigZag Arrays I
+#include "leetcode.h"
+
+/*
+ * you are given three integers. a zigzag array of length 'n' is defined as
+ * follows: each element lies in the '[l, r]', no two adjacent elements are
+ * equal, and no three consecutive elements form a strickly increasing or
+ * decreasing sequence. return the totla number of valid zigzag arrays. since
+ * the answer may be very large, return it modulo 10^9+7.
+ */
+
+int zigZagArrays(int n, int l, int r) {
+  int mod = 1e9 + 7, m = r - l + 1;
+  long long *dp0 = (long long *)malloc(m * sizeof(long long));
+  long long *dp1 = (long long *)malloc(m * sizeof(long long));
+  long long *pref = (long long *)malloc(m * sizeof(long long));
+  for (int i = 0; i < m; i++)
+    dp0[i] = 1;
+  for (int i = 2; i <= n; i++) {
+    pref[0] = dp0[0];
+    for (int j = 1; j < m; j++)
+      pref[j] = (pref[j - 1] + dp0[j]) % mod;
+    for (int j = 0; j < m; j++)
+      dp1[j] = 0;
+    if (!(i % 2)) {
+      for (int j = 1; j < m; j++)
+        dp1[j] = pref[j - 1];
+    } else {
+      long long total = pref[m - 1];
+      for (int j = 0; j < m - 1; j++)
+        dp1[j] = (total - pref[j] + mod) % mod;
+    }
+    long long *tmp = dp0;
+    dp0 = dp1;
+    dp1 = tmp;
+  }
+  long long ans = 0;
+  for (int i = 0; i < m; i++)
+    ans = (ans + dp0[i]) % mod;
+  free(dp0);
+  free(dp1);
+  free(pref);
+  return ans * 2 % mod;
+}
+
+int main() {
+  int r1 = zigZagArrays(3, 4, 5);
+  int r2 = zigZagArrays(3, 1, 3);
+  printf("%d\n", r1);
+  assert(r1 == 2);
+  printf("%d\n", r2);
+  assert(r2 == 10);
+}
diff --git a/num_zigzag_arrays1.py b/num_zigzag_arrays1.py
@@ -0,0 +1,28 @@
+# 3699. Number of ZigZag Arrays I
+
+"""
+you are given three integers. a zigzag array of length 'n' is defined as
+follows: each element lies in the '[l, r]', no two adjacent elements are
+equal, and no three consecutive elements form a strickly increasing or
+decreasing sequence. return the totla number of valid zigzag arrays. since
+the answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution:
+    def zigZagArrays(self, n: int, l: int, r: int) -> int:
+        mod = 10**9 + 7
+        m = r - l + 1
+        dp = [1] * m
+        for i in range(2, n + 1):
+            dp.reverse()
+            total = 0
+            for j in range(m):
+                dp[j], total = total, (total + dp[j]) % mod
+        return (sum(dp) % mod << 1) % mod
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.zigZagArrays(n=3, l=4, r=5))
+    print(obj.zigZagArrays(n=3, l=1, r=3))