Count of Arrays of size N having absolute difference between adjacent elements at most 1 | Function to find the count of possible arrays such that the absolute difference between any adjacent elements is atmost 1 ; Stores the dp states where dp [ i ] [ j ] represents count of arrays of length i + 1 having their last element as j ; Case where 1 st array element is missing ; All integers in range [ 1 , M ] are reachable ; Only reachable integer is arr [ 0 ] ; Iterate through all values of i ; If arr [ i ] is not missing ; Only valid value of j is arr [ i ] ; If arr [ i ] is missing ; Iterate through all possible values of j in range [ 1 , M ] ; Stores the count of valid arrays ; Calculate the total count of valid arrays ; Return answer ; Driver Code ; Function Call
function countArray ( arr , N , M ) { let dp = new Array ( N ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( M + 2 ) . fill ( 0 ) ; } if ( arr [ 0 ] == - 1 ) { for ( let j = 1 ; j <= M ; j ++ ) { dp [ 0 ] [ j ] = 1 ; } } else { dp [ 0 ] [ arr [ 0 ] ] = 1 ; } for ( let i = 1 ; i < N ; i ++ ) { if ( arr [ i ] != - 1 ) { let j = arr [ i ] ; dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] ; } if ( arr [ i ] == - 1 ) { for ( let j = 1 ; j <= M ; j ++ ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] ; } } } let arrCount = 0 ; for ( let j = 1 ; j <= M ; j ++ ) { arrCount += dp [ N - 1 ] [ j ] ; } return arrCount ; } let arr = [ 4 , - 1 , 2 , 1 , - 1 , - 1 ] ; let N = arr . length ; let M = 10 ; document . write ( countArray ( arr , N , M ) ) ;