# Find the Count of Monotonic Pairs I
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-count-of-monotonic-pairs-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-count-of-monotonic-pairs-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
You are given an array of **positive** integers `nums` of length `n`.

We call a pair of **non-negative** integer arrays `(arr1, arr2)` **monotonic** if:

* The lengths of both arrays are `n`.
* `arr1` is monotonically **non-decreasing**, in other words, `arr1[0] <= arr1[1] <= ... <= arr1[n - 1]`.
* `arr2` is monotonically **non-increasing**, in other words, `arr2[0] >= arr2[1] >= ... >= arr2[n - 1]`.
* `arr1[i] + arr2[i] == nums[i]` for all `0 <= i <= n - 1`.

Return the count of **monotonic** pairs.

Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[2,3,2\]

**Output:** 4

**Explanation:**

The good pairs are:

1. `([0, 1, 1], [2, 2, 1])`
2. `([0, 1, 2], [2, 2, 0])`
3. `([0, 2, 2], [2, 1, 0])`
4. `([1, 2, 2], [1, 1, 0])`

**Example 2:**

**Input:** nums = \[5,5,5,5\]

**Output:** 126

**Constraints:**

* `1 <= n == nums.length <= 2000`
* `1 <= nums[i] <= 50`

# Approaches
## Naive Dynamic Programming
This approach uses dynamic programming to solve the problem. We define a 2D DP table, `dp[i][j]`, to store the number of valid monotonic arrays `arr1` of length `i+1` (from index 0 to `i`) where the last element `arr1[i]` is equal to `j`. We build this table iteratively for each index `i` from 0 to `n-1` by checking all valid transitions from the previous state.
**Time:** O(n * M^2), where `n` is the length of `nums` and `M` is the maximum value in `nums`. We have three nested loops: over `i` (size `n`), `j` (size `M`), and `k` (size `M`). · **Space:** O(n * M), where `n` is the length of `nums` and `M` is the maximum value in `nums`. This is for the 2D DP table.
**Pros:** It's a straightforward DP solution that correctly models the problem's state transitions.; More efficient than a pure recursive or backtracking approach.
**Cons:** The time complexity of O(n * M^2) can be too slow if M is large, although it passes for the given constraints.; The space complexity of O(n * M) can be substantial for large n.
### Explanation
First, we rephrase the problem's conditions in terms of `arr1` only. The condition `arr1[i] + arr2[i] == nums[i]` and `arr2` being non-increasing implies `nums[i] - arr1[i] >= nums[i+1] - arr1[i+1]`, which simplifies to `arr1[i+1] >= arr1[i] + nums[i+1] - nums[i]`. Combined with `arr1` being non-decreasing (`arr1[i+1] >= arr1[i]`), we get a single condition for the transition from `arr1[i]` to `arr1[i+1]`: `arr1[i+1] >= max(arr1[i], arr1[i] + nums[i+1] - nums[i])`.

We can define a DP state `dp[i][j]` as the number of ways to form a valid prefix `arr1[0...i]` such that `arr1[i] = j`. To compute `dp[i][j]`, we sum up `dp[i-1][k]` for all values `k` that could have been `arr1[i-1]`. This involves a nested loop structure, leading to a cubic-like complexity.

**Algorithm Steps:**
1.  Let `M` be the maximum value in `nums`. Create a DP table `dp[n][M+1]`.
2.  **Base Case (i=0):** For `j` from `0` to `nums[0]`, set `dp[0][j] = 1`, as any of these values is a valid start.
3.  **Transitions (i > 0):** For `i` from `1` to `n-1`, and for each `j` from `0` to `nums[i]`:
    - Iterate `k` from `0` to `nums[i-1]`.
    - If `j` is a valid successor to `k` (i.e., `j >= k` and `j >= k + nums[i] - nums[i-1]`), add `dp[i-1][k]` to `dp[i][j]`, taking the result modulo `10^9 + 7`.
4.  **Final Result:** Sum up all values in `dp[n-1]` up to index `nums[n-1]` to get the total count.

```java
class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        long[][] dp = new long[n][maxVal + 1];
        int MOD = 1_000_000_007;

        // Base case: i = 0
        for (int j = 0; j <= nums[0]; j++) {
            dp[0][j] = 1;
        }

        // Fill DP table for i > 0
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= nums[i]; j++) {
                long diff = (long)nums[i] - nums[i-1];
                for (int k = 0; k <= nums[i-1]; k++) {
                    if (j >= k && j >= k + diff) {
                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
                    }
                }
            }
        }

        // Calculate the final result
        long totalCount = 0;
        for (int j = 0; j <= nums[n - 1]; j++) {
            totalCount = (totalCount + dp[n - 1][j]) % MOD;
        }

        return (int) totalCount;
    }
}
```
### Algorithm
- Define a 2D DP array `dp[i][j]` to store the number of valid `arr1` prefixes of length `i+1` where `arr1[i] = j`.
- The state transition relies on the conditions derived from the problem: `arr1[i+1] >= max(arr1[i], arr1[i] + nums[i+1] - nums[i])`.
- Initialize the base case for `i=0`: `dp[0][j] = 1` for `0 <= j <= nums[0]`.
- Iterate from `i = 1` to `n-1`:
  - For each possible value `j` of `arr1[i]` (from `0` to `nums[i]`):
    - Iterate through all possible values `k` of `arr1[i-1]` (from `0` to `nums[i-1]`):
      - If `k` can transition to `j`, add `dp[i-1][k]` to `dp[i][j]`.
- The final answer is the sum of `dp[n-1][j]` for all valid `j`.

## Dynamic Programming with Prefix Sums
This approach optimizes the naive DP solution by observing that the inner loop is calculating a sum over a range. Such summations can be computed efficiently using prefix sums. By pre-calculating the prefix sums for each row of the DP table, we can determine the value of any `dp[i][j]` in constant time, which significantly improves the overall time complexity.
**Time:** O(n * M). For each of the `n` states, we perform O(M) work to compute the DP values and their prefix sums. · **Space:** O(n * M), for the DP and prefix sum tables.
**Pros:** Much faster than the naive DP approach, with a time complexity of O(n * M).; Handles the given constraints very efficiently.
**Cons:** Requires additional space for the prefix sum table, although the asymptotic space complexity remains the same.
### Explanation
The key insight is that the transition `dp[i][j] = sum(dp[i-1][k])` is performed for `k` in the range `[0, limit]`, where `limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1]))`. This is a prefix sum.

We can maintain a parallel 2D array, `ps`, where `ps[i][x]` stores the sum of `dp[i][k]` for `k` from `0` to `x`. After computing the `i-1`-th row of the `dp` table, we can compute the `i-1`-th row of the `ps` table in `O(M)` time. Then, when computing the `i`-th row of `dp`, each `dp[i][j]` can be found in `O(1)` by looking up the precomputed value in `ps[i-1]`, effectively eliminating one loop from the previous approach.

**Algorithm Steps:**
1.  Create a DP table `dp[n][M+1]` and a prefix sum table `ps[n][M+1]`.
2.  **Base Case (i=0):** Fill `dp[0]` and `ps[0]` as before.
3.  **Transitions (i > 0):** For `i` from `1` to `n-1`:
    - For each `j` from `0` to `nums[i]`:
        - Calculate the upper bound for `k`: `limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1]))`.
        - If `limit >= 0`, set `dp[i][j] = ps[i-1][limit]`.
    - Compute the prefix sums for the new `dp[i]` row and store them in `ps[i]`.
4.  **Final Result:** The answer is `ps[n-1][nums[n-1]]`.

```java
class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        long[][] dp = new long[n][maxVal + 1];
        long[][] ps = new long[n][maxVal + 1];
        int MOD = 1_000_000_007;

        // Base case: i = 0
        for (int j = 0; j <= nums[0]; j++) {
            dp[0][j] = 1;
        }
        ps[0][0] = dp[0][0];
        for (int j = 1; j <= maxVal; j++) {
            ps[0][j] = (ps[0][j - 1] + dp[0][j]) % MOD;
        }

        // Fill DP table for i > 0
        for (int i = 1; i < n; i++) {
            long diff = (long)nums[i] - nums[i-1];
            for (int j = 0; j <= nums[i]; j++) {
                long k_upper_bound = j - Math.max(0, diff);
                long limit = Math.min(nums[i-1], k_upper_bound);
                
                if (limit >= 0) {
                    dp[i][j] = ps[i-1][(int)limit];
                }
            }
            
            ps[i][0] = dp[i][0];
            for (int j = 1; j <= maxVal; j++) {
                ps[i][j] = (ps[i][j - 1] + dp[i][j]) % MOD;
            }
        }

        return (int) ps[n - 1][nums[n - 1]];
    }
}
```
### Algorithm
- The DP state `dp[i][j]` is the same as the naive approach.
- The transition `dp[i][j] = sum(dp[i-1][k])` is over a contiguous range of `k`.
- The upper bound for `k` is `limit = min(nums[i-1], j - max(0, nums[i] - nums[i-1]))`.
- We can precompute prefix sums for each row `i-1` of the DP table into an array `ps[i-1]`.
- `dp[i][j]` can then be found in O(1) time using `ps[i-1][limit]`.
- This removes the innermost loop from the naive DP approach.

## Space-Optimized Dynamic Programming
This is the most efficient approach, building upon the prefix sum optimization to also reduce space complexity. We notice that to compute the DP values for the current index `i`, we only need the prefix sums from the previous index `i-1`. This allows us to discard the full 2D DP table and use only a few 1D arrays to store the states for the previous and current rows, reducing space complexity from O(n * M) to O(M).
**Time:** O(n * M). The time complexity remains the same as the previous approach, as the core computation is unchanged. · **Space:** O(M), where `M` is the maximum value in `nums`. We only need a few arrays of size `M+1` regardless of `n`.
**Pros:** Optimal time complexity for this DP formulation.; Optimal space complexity, making it very memory-efficient.
**Cons:** The implementation can be slightly more complex due to managing and updating the arrays representing the current and previous states.
### Explanation
We can optimize the space usage of the previous approach. The calculation for row `i` only depends on row `i-1`. Therefore, we don't need to store all `n` rows. We can use two 1D arrays: one to store the DP values of the previous state (`dp`) and another for its prefix sums (`ps`). In each step of the iteration over `i`, we compute the DP values for the current state into a temporary array (`next_dp`) using the `ps` array of the previous state. Then, we replace `dp` with `next_dp` and update the `ps` array for the next iteration.

**Algorithm Steps:**
1.  Initialize 1D arrays `dp[M+1]` and `ps[M+1]`.
2.  **Base Case (i=0):** Populate `dp` for `i=0` and compute its prefix sums into `ps`.
3.  **Transitions (i > 0):** For `i` from `1` to `n-1`:
    - Create a new array `next_dp[M+1]`.
    - For each `j` from `0` to `nums[i]`, calculate `next_dp[j]` using the `ps` array (which holds data for `i-1`).
    - After the loop, set `dp = next_dp`.
    - Recompute the `ps` array from the new `dp` array.
4.  **Final Result:** After the main loop finishes, the answer is the value in `ps[nums[n-1]]`.

```java
class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        int MOD = 1_000_000_007;

        long[] dp = new long[maxVal + 1];
        long[] ps = new long[maxVal + 1];

        // Base case: i = 0
        for (int j = 0; j <= nums[0]; j++) {
            dp[j] = 1;
        }
        
        ps[0] = dp[0];
        for (int j = 1; j <= maxVal; j++) {
            ps[j] = (ps[j - 1] + dp[j]) % MOD;
        }

        // Fill DP table for i > 0
        for (int i = 1; i < n; i++) {
            long[] next_dp = new long[maxVal + 1];
            long diff = (long)nums[i] - nums[i-1];
            for (int j = 0; j <= nums[i]; j++) {
                long k_upper_bound = j - Math.max(0, diff);
                long limit = Math.min(nums[i-1], k_upper_bound);
                
                if (limit >= 0) {
                    next_dp[j] = ps[(int)limit];
                }
            }
            
            dp = next_dp;
            ps[0] = dp[0];
            for (int j = 1; j <= maxVal; j++) {
                ps[j] = (ps[j - 1] + dp[j]) % MOD;
            }
        }

        return (int) ps[nums[n - 1]];
    }
}
```
### Algorithm
- The logic is identical to the prefix sum optimization.
- Observe that computing `dp[i]` only requires `ps[i-1]` (the prefix sums of `dp[i-1]`).
- Instead of using 2D arrays `dp[n][M]` and `ps[n][M]`, we use 1D arrays `dp` and `ps` of size `M`.
- In each iteration `i`, `ps` holds the prefix sums from iteration `i-1`. We use it to compute a `next_dp` array.
- After `next_dp` is computed, it becomes the new `dp` for the next iteration, and we update `ps` based on it.

# Solutions
### Java

```java
class Solution { public int countOfPairs ( int [] nums ) { final int mod = ( int ) 1 e9 + 7 ; int n = nums . length ; int m = Arrays . stream ( nums ). max (). getAsInt (); int [][] f = new int [ n ][ m + 1 ]; for ( int j = 0 ; j <= nums [ 0 ]; ++ j ) { f [ 0 ][ j ] = 1 ; } int [] g = new int [ m + 1 ]; for ( int i = 1 ; i < n ; ++ i ) { g [ 0 ] = f [ i - 1 ][ 0 ]; for ( int j = 1 ; j <= m ; ++ j ) { g [ j ] = ( g [ j - 1 ] + f [ i - 1 ][ j ]) % mod ; } for ( int j = 0 ; j <= nums [ i ]; ++ j ) { int k = Math . min ( j , j + nums [ i - 1 ] - nums [ i ]); if ( k >= 0 ) { f [ i ][ j ] = g [ k ]; } } } int ans = 0 ; for ( int j = 0 ; j <= nums [ n - 1 ]; ++ j ) { ans = ( ans + f [ n - 1 ][ j ]) % mod ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int countOfPairs ( vector < int >& nums ) { const int mod = 1e9 + 7 ; int n = nums . size (); int m = * max_element ( nums . begin (), nums . end ()); vector < vector < int >> f ( n , vector < int > ( m + 1 )); for ( int j = 0 ; j <= nums [ 0 ]; ++ j ) { f [ 0 ][ j ] = 1 ; } vector < int > g ( m + 1 ); for ( int i = 1 ; i < n ; ++ i ) { g [ 0 ] = f [ i - 1 ][ 0 ]; for ( int j = 1 ; j <= m ; ++ j ) { g [ j ] = ( g [ j - 1 ] + f [ i - 1 ][ j ]) % mod ; } for ( int j = 0 ; j <= nums [ i ]; ++ j ) { int k = min ( j , j + nums [ i - 1 ] - nums [ i ]); if ( k >= 0 ) { f [ i ][ j ] = g [ k ]; } } } int ans = 0 ; for ( int j = 0 ; j <= nums [ n - 1 ]; ++ j ) { ans = ( ans + f [ n - 1 ][ j ]) % mod ; } return ans ; } };
```

### Python

```python
class Solution : def countOfPairs ( self , nums : List [ int ]) -> int : mod = 10 ** 9 + 7 n , m = len ( nums ), max ( nums ) f = [[ 0 ] * ( m + 1 ) for _ in range ( n )] for j in range ( nums [ 0 ] + 1 ): f [ 0 ][ j ] = 1 for i in range ( 1 , n ): s = list ( accumulate ( f [ i - 1 ])) for j in range ( nums [ i ] + 1 ): k = min ( j , j + nums [ i - 1 ] - nums [ i ]) if k >= 0 : f [ i ][ j ] = s [ k ] % mod return sum ( f [ - 1 ][: nums [ - 1 ] + 1 ]) % mod
```