Array Description

Task:

You know that an array has $n$ integers between $1$ and $m$, and the absolute difference between two adjacent values is at most $1$.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers $n$ and $m$: the array size and the upper bound for each value.

The next line has $n$ integers $x_1,x_2,\dots,x_n$: the contents of the array. Value $0$ denotes an unknown value.

Output

Print one integer: the number of arrays modulo $10^9+7$.

Constraints

• $1 \le n \le 10^5$
  
• $1 \le m \le 100$
  
• $0 \le x_i \le m$
  

After minute of thinking, the first thing springs to my mind is Dynamic Programming. And how could I think of DP as first glance? Well, not sure about that, but everything that could be divided into independently subproblem, belongs in DP category.

This problem can be splitted up by the way of reducing the original array length. For more precise, instead of calculating $array[:n]$'s result directly, we can do it through $array[:n-1]$. And keep doing it repeatedly until reaching $array[:1]$.

Next, what is subarray's result ? It is the count of number that can be present in current index. Or, more accurately, it's a dictionary with key is all posible number that index i can be assigned, and value is its number of occurances.
For example:
If value at index $i$ is 2, then valid numbers for index $i-1$ will stay in range [1,2,3]. That also means we just take the dictionary's $i-1$ with all keys in range [1,2,3] into account. Finally, we accumulate all valid combination that can be made by dictionary's $i-1$ to get dictionary's $i$. One thing to keep in mind is the value $0$. With this special and tough case, our strategy is keeping all keys in the dictionary's $i-1$ and with each of key, generating 3 new valid keys in range [key-1,key,key+1].

For particular example:
We have an array $input=[2, 0, 2, 0]$

 1import java.util.ArrayList;
 2import java.util.Arrays;
 3import java.util.HashSet;
 4import java.util.LinkedList;
 5import java.io.BufferedReader;
 6import java.io.IOException;
 7import java.io.InputStreamReader;
 8import java.util.StringTokenizer;
 9    
10public class Main {
11    public static int module = 1000000000 + 7;
12    
13    public static void main(String[] args) throws IOException {
14        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
15        StringTokenizer st = new StringTokenizer(br.readLine());
16        int n = Integer.parseInt(st.nextToken());
17        int m = Integer.parseInt(st.nextToken());
18        int[] arr = new int[n];
19        st = new StringTokenizer(br.readLine());
20        for (int i = 0; i < n; i++) {
21            arr[i] = Integer.parseInt(st.nextToken());
22        }
23        int[] dp = new int[m+2];
24        Arrays.fill(dp, 0);
25        for (int i = 0; i < arr.length; i++) {
26            if(i==0){
27                if (arr[i] == 0) {
28                    Arrays.fill(dp,1);
29                    dp[0]=0;
30                    dp[m+1]=0;
31                }
32                else{
33                    dp[arr[i]]=1;
34                }
35                continue;
36            }
37            if (arr[i] == 0) {
38                int[] dp1 = new int[m+2];
39                Arrays.fill(dp1, 0);
40                for (int j = 1; j < (m+1); j++) {
41                    dp1[j]=((dp[j] + dp[j-1])%module + dp[j+1])%module;
42                }
43                dp=dp1;
44            } else {
45                int tmp = ((dp[arr[i]] + dp[arr[i] - 1])%module + dp[arr[i] + 1])%module;
46                Arrays.fill(dp, 0);
47                dp[arr[i]] = tmp;
48            }
49        }
50        int ans=0;
51        for (int i = 0; i < dp.length; i++) {
52            ans+=dp[i];
53            ans%=module;
54        }
55        System.out.println(ans);
56    }
57}
58        

Time complexity: O(N). Coz we go through the array only once.

Space complexity: We need a dictionary to store count of number. O(m) and m is fixed => O(1).