Welcome to Subscribe On Youtube

3699. Number of ZigZag Arrays I

Description

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

• Each element lies in the range [l, r].
• No two adjacent elements are equal.
• No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 109 + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

 

Example 1:

Input: n = 3, l = 4, r = 5

Output: 2

Explanation:

There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:

• [4, 5, 4]
• [5, 4, 5]​​​​​​​

Example 2:

Input: n = 3, l = 1, r = 3

Output: 10

Explanation:

There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:

• [1, 2, 1], [1, 3, 1], [1, 3, 2]
• [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
• [3, 1, 2], [3, 1, 3], [3, 2, 3]

All arrays meet the ZigZag conditions.

 

Constraints:

• 3 <= n <= 2000
• 1 <= l < r <= 2000

Solutions

Solution 1

• C
• Java
• C++
• Python
• Go

• int zigZagArrays(int n, int low, int high) {
      int range = high - low;
      int mod = 1000000007, *dp, *ptr, *end, i = 1, goingUp = 1;
      long long ans = 0;
      if (range < 1 || !(dp = malloc(range * sizeof(int)))) return 0;
      ptr = dp;
      end = dp + range;
      while (ptr < end) *ptr++ = 1;
      ptr = dp + 1;
      while (ptr < end) *ptr += ptr[-1], ptr++;
      for (; i < n - 1; i++) {
          if (goingUp) {
              ptr = dp + range - 2;
              while (ptr >= dp) *ptr += ptr[1], *ptr -= *ptr >= mod ? mod : 0, ptr--;
          } else {
              ptr = dp + 1;
              while (ptr < end) *ptr += ptr[-1], *ptr -= *ptr >= mod ? mod : 0, ptr++;
          }
          goingUp ^= 1;
      }
      ptr = dp;
      while (ptr < end) ans += *ptr++;
      free(dp);
      return (int) (ans * 2 % mod);
  }
  
  

• class Solution {
      public int zigZagArrays(int n, int l, int r) {
          final int mod = (int) 1e9 + 7;
          int m = r - l + 1;
          long[] up = new long[m];
          long[] down = new long[m];
          Arrays.fill(up, 1);
          Arrays.fill(down, 1);
          for (int k = 1; k < n; ++k) {
              long[] pre = new long[m + 1];
              long[] suf = new long[m + 1];
              for (int i = 0; i < m; ++i) {
                  pre[i + 1] = (pre[i] + down[i]) % mod;
              }
              for (int i = m - 1; i >= 0; --i) {
                  suf[i] = (suf[i + 1] + up[i]) % mod;
              }
              for (int i = 0; i < m; ++i) {
                  up[i] = pre[i];
                  down[i] = suf[i + 1];
              }
          }
          long ans = 0;
          for (int i = 0; i < m; ++i) {
              ans = (ans + up[i] + down[i]) % mod;
          }
          return (int) ans;
      }
  }
  
  

• class Solution {
  public:
      int zigZagArrays(int n, int l, int r) {
          const int mod = 1e9 + 7;
          int m = r - l + 1;
          vector<long long> up(m, 1), down(m, 1);
          for (int k = 1; k < n; ++k) {
              vector<long long> pre(m + 1), suf(m + 1);
              for (int i = 0; i < m; ++i) {
                  pre[i + 1] = (pre[i] + down[i]) % mod;
              }
              for (int i = m - 1; i >= 0; --i) {
                  suf[i] = (suf[i + 1] + up[i]) % mod;
              }
              for (int i = 0; i < m; ++i) {
                  up[i] = pre[i];
                  down[i] = suf[i + 1];
              }
          }
          long long ans = 0;
          for (int i = 0; i < m; ++i) {
              ans = (ans + up[i] + down[i]) % mod;
          }
          return ans;
      }
  };
  
  

• class Solution:
      def zigZagArrays(self, n: int, l: int, r: int) -> int:
          mod = 10**9 + 7
          m = r - l + 1
          up = [1] * m
          down = [1] * m
          for _ in range(n - 1):
              pre = [0] * (m + 1)
              suf = [0] * (m + 1)
              for i in range(m):
                  pre[i + 1] = (pre[i] + down[i]) % mod
              for i in range(m - 1, -1, -1):
                  suf[i] = (suf[i + 1] + up[i]) % mod
              up = pre[:m]
              down = suf[1:]
          return sum(up + down) % mod
  
  

• func zigZagArrays(n int, l int, r int) int {
  	const mod = int64(1e9 + 7)
  	m := r - l + 1
  	up := make([]int64, m)
  	down := make([]int64, m)
  	for i := range up {
  		up[i], down[i] = 1, 1
  	}
  	for k := 1; k < n; k++ {
  		pre := make([]int64, m+1)
  		suf := make([]int64, m+1)
  		for i := 0; i < m; i++ {
  			pre[i+1] = (pre[i] + down[i]) % mod
  		}
  		for i := m - 1; i >= 0; i-- {
  			suf[i] = (suf[i+1] + up[i]) % mod
  		}
  		for i := 0; i < m; i++ {
  			up[i] = pre[i]
  			down[i] = suf[i+1]
  		}
  	}
  	var ans int64
  	for i := 0; i < m; i++ {
  		ans = (ans + up[i] + down[i]) % mod
  	}
  	return int(ans)
  }
  
  

All Problems

All Solutions