# Find the Count of Monotonic Pairs II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-count-of-monotonic-pairs-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-count-of-monotonic-pairs-ii
**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:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon)
---
## 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] <= 1000`

# Approaches
## Naive Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define a DP state `dp[i][j]` as the number of ways to form a valid prefix of `arr1` of length `i+1` where `arr1[i]` is equal to `j`. The DP table is built iteratively from `i=0` to `n-1` by summing up possibilities from the previous state, leading to a cubic-like time complexity.
**Time:** O(n * max_val^2), where `n` is the length of `nums` and `max_val` is the maximum value in `nums`. The three nested loops (over `i`, `j`, and `k`) lead to this complexity. · **Space:** O(max_val), where `max_val` is the maximum value in `nums`. We use two arrays of size `max_val + 1` to store DP states for the current and previous indices.
**Pros:** Conceptually simple and a direct application of dynamic programming.; Correctly models the problem's state transitions.
**Cons:** Highly inefficient due to the nested loop for summation in the transition.; The time complexity is too high for the given constraints, which will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The core idea is to count the number of valid sequences for `arr1` up to each index `i`, as the constraints on `arr2` can be fully translated into constraints on `arr1`. Let `dp[i][j]` be the number of ways to choose `arr1[0], arr1[1], ..., arr1[i]` satisfying all monotonic conditions, with `arr1[i] = j`.

**Base Case:** For the first element `i=0`, `arr1[0]` can be any integer from `0` to `nums[0]`. Thus, `dp[0][j] = 1` for `0 <= j <= nums[0]`.

**Transition:** To compute `dp[i][j]`, we sum up `dp[i-1][k]` over all valid previous values `k = arr1[i-1]`. The conditions for `k` given `arr1[i]=j` are:
- `0 <= k <= nums[i-1]`
- `k <= j` (for `arr1` to be non-decreasing)
- `nums[i-1] - k >= nums[i] - j` (for `arr2` to be non-increasing), which simplifies to `k <= j + nums[i-1] - nums[i]`.

This leads to the transition: `dp[i][j] = sum(dp[i-1][k])` for all `k` from `0` to `min(nums[i-1], j, j + nums[i-1] - nums[i])`. This summation is performed in a loop, making the transition slow. For space optimization, we only need to store the DP states for the previous and current index, so we can use two arrays instead of a full 2D table.

```java
class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;

        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

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

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

        // Iterate from i = 1 to n-1
        for (int i = 1; i < n; i++) {
            long[] newDp = new long[maxVal + 1];
            for (int j = 0; j <= nums[i]; j++) {
                long sum = 0;
                int upperK = Math.min(j, j + nums[i - 1] - nums[i]);
                upperK = Math.min(upperK, nums[i - 1]);
                
                for (int k = 0; k <= upperK; k++) {
                    sum = (sum + dp[k]) % MOD;
                }
                newDp[j] = sum;
            }
            dp = newDp;
        }

        long totalCount = 0;
        for (int j = 0; j <= maxVal; j++) {
            totalCount = (totalCount + dp[j]) % MOD;
        }

        return (int) totalCount;
    }
}
```
### Algorithm
1. **Initialization**: Set `MOD = 10^9 + 7`. Find `max_val`, the maximum value in `nums`. Initialize a DP array `dp` of size `max_val + 1` to store the counts for the previous index `i-1`.
2. **Base Case (i=0)**: For `arr1[0]`, any value `j` from `0` to `nums[0]` is valid. So, initialize `dp[j] = 1` for `0 <= j <= nums[0]`.
3. **Iteration**: Loop for `i` from `1` to `n-1`:
    a. Create a `new_dp` array of size `max_val + 1` for the current index `i`.
    b. Loop for `j` from `0` to `nums[i]` (representing `arr1[i]`):
        i. Determine the valid range for `arr1[i-1]`. The value `k = arr1[i-1]` must be less than or equal to `upper_k = min(nums[i-1], j, j + nums[i-1] - nums[i])`.
        ii. Calculate `new_dp[j]` by summing `dp[k]` for all `k` from `0` to `upper_k`.
    c. Replace `dp` with `new_dp` for the next iteration.
4. **Result**: The total count is the sum of all values in the final `dp` array (for `i=n-1`), modulo `MOD`.

## Dynamic Programming with Prefix Sum Optimization
This approach significantly improves upon the naive DP solution by optimizing the transition step. The summation required to calculate `dp[i][j]` is recognized as a prefix sum of the previous DP state `dp[i-1]`. By pre-calculating these prefix sums in each step, we can reduce the time to compute each `dp[i][j]` from `O(max_val)` to `O(1)`, making the overall solution much more efficient.
**Time:** O(n * max_val). For each of the `n-1` iterations, we compute prefix sums (`O(max_val)`) and then the new DP row (`O(max_val)`). This results in a total time complexity of `O(n * max_val)`. · **Space:** O(max_val). We use arrays for `dp`, `newDp`, and `prefixSum`, each of size proportional to `max_val`.
**Pros:** Significantly more efficient than the naive approach.; Passes within the time limits for the given constraints.; Optimal time and space complexity for this DP formulation.
**Cons:** Requires careful handling of indices and modulo arithmetic.; The logic, while efficient, might be slightly less intuitive at first glance than the naive summation.
### Explanation
This method uses the same DP state definition as the naive approach but optimizes the calculation. The transition `dp[i][j] = sum_{k=0}^{upper_k} dp[i-1][k]` involves a sum over a contiguous range, which is a classic pattern for prefix sum optimization.

Instead of re-calculating this sum for every `j`, we first compute a `prefix_sum` array for the `dp[i-1]` state. Let `prefix_sum[x] = sum_{k=0}^{x} dp[i-1][k]`. This array can be computed for all `x` in `O(max_val)` time.

With the `prefix_sum` array available, the transition for `dp[i][j]` becomes a simple `O(1)` lookup: `dp[i][j] = prefix_sum[upper_k]`, where `upper_k` is the same upper bound calculated in the naive approach. This reduces the complexity of the inner part of the main loop, leading to a much faster overall algorithm that fits within the time limits.

```java
class Solution {
    public int countMonotonicPairs(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;

        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

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

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

        // Iterate from i = 1 to n-1
        for (int i = 1; i < n; i++) {
            // Calculate prefix sums for the previous dp state
            long[] prefixSum = new long[maxVal + 1];
            prefixSum[0] = dp[0];
            for (int k = 1; k <= maxVal; k++) {
                prefixSum[k] = (prefixSum[k - 1] + dp[k]) % MOD;
            }

            long[] newDp = new long[maxVal + 1];
            for (int j = 0; j <= nums[i]; j++) {
                int upperK = Math.min(j, j + nums[i - 1] - nums[i]);
                upperK = Math.min(upperK, nums[i - 1]);
                
                if (upperK >= 0) {
                    newDp[j] = prefixSum[upperK];
                }
            }
            dp = newDp;
        }

        long totalCount = 0;
        for (int j = 0; j <= maxVal; j++) {
            totalCount = (totalCount + dp[j]) % MOD;
        }

        return (int) totalCount;
    }
}
```
### Algorithm
1. **Initialization**: Set `MOD = 10^9 + 7`. Find `max_val`, the maximum value in `nums`. Initialize a DP array `dp` of size `max_val + 1`.
2. **Base Case (i=0)**: For `arr1[0]`, any value `j` from `0` to `nums[0]` is valid. So, initialize `dp[j] = 1` for `0 <= j <= nums[0]`.
3. **Iteration**: Loop for `i` from `1` to `n-1`:
    a. Create a `prefix_sum` array from the current `dp` array. `prefix_sum[k]` will store the sum of `dp[0...k]`.
    b. Create a `new_dp` array for the current index `i`.
    c. Loop for `j` from `0` to `nums[i]` (representing `arr1[i]`):
        i. Determine the upper bound `upper_k` for `arr1[i-1]`'s value.
        ii. Set `new_dp[j] = prefix_sum[upper_k]`. This is an O(1) lookup.
    d. Replace `dp` with `new_dp` for the next iteration.
4. **Result**: The total count is the sum of all values in the final `dp` array, modulo `MOD`.

# 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

```