Given two arrays arr1[] and arr2[] having N integers in non-decreasing order, the task is to find the count of non-decreasing arrays arr3[] of length N such that arr1[i] <= arr3[i] <= arr2[i] for all values of i in range [0, N).
Examples:
Input: arr1[] = {1, 1}, arr2[] = {2, 3}
Output: 5
Explanation: The 5 possible arrays that follow the required conditions are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}Input: ranges[] = {{-12, 15}, {3, 9}, {-5, -2}, {20, 25}, {16, 20}}
Output: 247
Approach: The given problem can be solved using Dynamic Programming. Consider a 2D array dp[][] such that dp[i][j] represents the count of arrays of length i such that the ith element is j. Initialize all the elements of the dp array as 0 and dp[0][0] as 1. Upon observation, the DP relation of the above problem can be stated as follows:
dp[i][j] =
![\sum_{x = arr1[i]}^{arr2[i]}dp[i-1][x] + dp[i][j-1]](https://cdn.geeksforgeeks.org/static/gallery/images/logo.png "Rendered by QuickLaTeX.com"){kind=logo}
Therefore, using the above relation, calculate the value of dp[i][j] for each i in the range [0, N] and for each j in the range [0, M] where M represents the maximum integer in both the given arrays arr1[] and arr2[]. Hence, the value stored in dp[N][M] is the required answer.
Below is the implementation of the above approach:
C++
// C++ Program of the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find the count of// valid sorted arraysint arrCount(int arr1[], int arr2[], int N){Â
    // Maximum possible value    // of arr1 and arr2    int M = 1000;Â
    // Stores the dp states    vector<vector<int> > dp(        N + 1,        vector<int>(M + 1, 0));Â
    // Initial condition    dp[0][0] = 1;Â
    // Loop to iterate over range [0, N]    for (int i = 0; i <= N; i++) {Â
        // Loop to iterate over        // the range [0, M]        for (int j = 0; j < M; j++) {            dp[i][j + 1] += dp[i][j];        }Â
        // If current index is not        // the final index        if (i != N) {Â
            // Loop to iterate in the            // range [arr1[i], arr2[i]]            for (int j = arr1[i]; j <= arr2[i]; j++)                dp[i + 1][j] += dp[i][j];        }    }Â
    // Return Answer    return dp[N][M];}Â
// Driver Codeint main(){Â Â Â Â int arr1[] = { 1, 1 };Â Â Â Â int arr2[] = { 2, 3 };Â Â Â Â int N = sizeof(arr1) / sizeof(int);Â
    cout << arrCount(arr1, arr2, N);Â
    return 0;} |
Java
// Java Program of the above approachimport java.util.*;Â
public class GFG{     // Function to find the count of// valid sorted arraysstatic int arrCount(int[] arr1, int[] arr2, int N){         // Maximum possible value    // of arr1 and arr2    int M = 1000;Â
    // Stores the dp states    int[][] dp = new int[N + 1][M + 1];Â
    // Initial condition    dp[0][0] = 1;Â
    // Loop to iterate over range [0, N]    for(int i = 0; i <= N; i++)     {                 // Loop to iterate over        // the range [0, M]        for(int j = 0; j < M; j++)        {            dp[i][j + 1] += dp[i][j];        }Â
        // If current index is not        // the final index        if (i != N)         {                         // Loop to iterate in the            // range [arr1[i], arr2[i]]            for(int j = arr1[i]; j <= arr2[i]; j++)                dp[i + 1][j] += dp[i][j];        }    }Â
    // Return Answer    return dp[N][M];}Â
// Driver Codepublic static void main(String args[]){Â Â Â Â int[] arr1 = { 1, 1 };Â Â Â Â int[] arr2 = { 2, 3 };Â Â Â Â int N = arr1.length;Â
    System.out.println(arrCount(arr1, arr2, N));}}Â
// This code is contributed by Samim Hossain Mondal. |
Python3
# Python Program to implement# the above approachÂ
# Function to find the count of# valid sorted arraysdef arrCount(arr1, arr2, N):Â
    # Maximum possible value    # of arr1 and arr2    M = 1000Â
    # Stores the dp states    dp = [0] * (N + 1)    for i in range(len(dp)):        dp[i] = [0] * (M + 1)Â
    # Initial condition    dp[0][0] = 1Â
    # Loop to iterate over range [0, N]    for i in range(N + 1):Â
        # Loop to iterate over        # the range [0, M]        for j in range(M):            dp[i][j + 1] += dp[i][j]Â
        # If current index is not        # the final index        if (i != N):Â
            # Loop to iterate in the            # range [arr1[i], arr2[i]]            for j in range(arr1[i], arr2[i] + 1):                dp[i + 1][j] += dp[i][j]Â
    # Return Answer    return dp[N][M]Â
# Driver Codearr1 = [1, 1]arr2 = [2, 3]N = len(arr1)Â
print(arrCount(arr1, arr2, N))Â
# This code is contributed by Saurabh Jaiswal |
C#
// C# Program of the above approachusing System;Â
class GFG{     // Function to find the count of// valid sorted arraysstatic int arrCount(int[] arr1, int[] arr2, int N){         // Maximum possible value    // of arr1 and arr2    int M = 1000;Â
    // Stores the dp states    int[,] dp = new int[N + 1, M + 1];Â
    // Initial condition    dp[0, 0] = 1;Â
    // Loop to iterate over range [0, N]    for(int i = 0; i <= N; i++)     {                 // Loop to iterate over        // the range [0, M]        for(int j = 0; j < M; j++)        {            dp[i, j + 1] += dp[i, j];        }Â
        // If current index is not        // the final index        if (i != N)         {                         // Loop to iterate in the            // range [arr1[i], arr2[i]]            for(int j = arr1[i]; j <= arr2[i]; j++)                dp[i + 1, j] += dp[i, j];        }    }Â
    // Return Answer    return dp[N, M];}Â
// Driver Codepublic static void Main(){Â Â Â Â int[] arr1 = { 1, 1 };Â Â Â Â int[] arr2 = { 2, 3 };Â Â Â Â int N = arr1.Length;Â
    Console.WriteLine(arrCount(arr1, arr2, N));}}Â
// This code is contributed by ukasp |
Javascript
<script>    // JavaScript Program to implement    // the above approach Â
    // Function to find the count of    // valid sorted arrays    function arrCount(arr1, arr2, N) {Â
        // Maximum possible value        // of arr1 and arr2        let M = 1000;Â
        // Stores the dp states        let dp = new Array(N + 1);        for (let i = 0; i < dp.length; i++) {            dp[i] = new Array(M + 1).fill(0);        }Â
        // Initial condition        dp[0][0] = 1;Â
        // Loop to iterate over range [0, N]        for (let i = 0; i <= N; i++) {Â
            // Loop to iterate over            // the range [0, M]            for (let j = 0; j < M; j++) {                dp[i][j + 1] += dp[i][j];            }Â
            // If current index is not            // the final index            if (i != N) {Â
                // Loop to iterate in the                // range [arr1[i], arr2[i]]                for (let j = arr1[i]; j <= arr2[i]; j++)                    dp[i + 1][j] += dp[i][j];            }        }Â
        // Return Answer        return dp[N][M];    }Â
    // Driver CodeÂ
    let arr1 = [1, 1];    let arr2 = [2, 3];    let N = arr1.length;Â
    document.write(arrCount(arr1, arr2, N));Â
// This code is contributed by Potta Lokesh</script> |
Output
5
Time Complexity: O(N * M), where M represents the maximum value of the integers in the array arr1[] and arr2[].
Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
