Count of non decreasing Arrays with ith element in range [ A [ i ] , B [ i ] ] | Function to count the total number of possible valid arrays ; Make a 2D DP table ; Make a 2D prefix sum table ; Base Case ; Initialize the prefix values ; Iterate over the range and update the dp table accordingly ; Add the dp values to the prefix sum ; Update the prefix sum table ; Find the result count of arrays formed ; Return the total count of arrays ; Driver Code
const totalValidArrays = ( a , b , N ) => { let dp = new Array ( N + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( b [ N - 1 ] + 1 ) . fill ( 0 ) ) ; let pref = new Array ( N + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( b [ N - 1 ] + 1 ) . fill ( 0 ) ) ; dp [ 0 ] [ 0 ] = 1 ; for ( let i = 0 ; i <= b [ N - 1 ] ; i ++ ) { pref [ 0 ] [ i ] = 1 ; } for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = a [ i - 1 ] ; j <= b [ i - 1 ] ; j ++ ) { dp [ i ] [ j ] += pref [ i - 1 ] [ j ] ; pref [ i ] [ j ] += dp [ i ] [ j ] ; } for ( let j = 0 ; j <= b [ N - 1 ] ; j ++ ) { if ( j > 0 ) { pref [ i ] [ j ] += pref [ i ] [ j - 1 ] ; } } } let ans = 0 ; for ( let i = a [ N - 1 ] ; i <= b [ N - 1 ] ; i ++ ) { ans += dp [ N ] [ i ] ; } return ans ; } let A = [ 1 , 1 ] ; let B = [ 2 , 3 ] ; let N = A . length ; document . write ( totalValidArrays ( A , B , N ) ) ;