Count of non-decreasing Arrays arr3[] such that arr1[i] <= arr3[i] <= arr2[i]

Namachila October 13, 2025

0 2 5 minutes read

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 i^th 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]$

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 arrays
int 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 Code
int 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 approach
import java.util.*;
 
public class GFG{
     
// Function to find the count of
// valid sorted arrays
static 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 Code
public 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 arrays
def 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 Code
arr1 = [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 approach
using System;
 
class GFG{
     
// Function to find the count of
// valid sorted arrays
static 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 Code
public 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

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 zambiatek!