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://geeksforgeeks.org/wp-content/uploads/2023/10/neveropen_quicklatex.com-b18dfefc1224d6fb1330f2aacf7e7d85_l3.png "Rendered by QuickLaTeX.com")
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> |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
