Problem statement

You are given an array nums of n positive integers.

A pair of non-negative integer arrays (arr1, arr2), each of length n, is called monotonic when:

• arr1 is non-decreasing: arr1[0] <= arr1[1] <= ... <= arr1[n - 1],
• arr2 is non-increasing: arr2[0] >= arr2[1] >= ... >= arr2[n - 1], and
• arr1[i] + arr2[i] == nums[i] for every index i.

Return the number of monotonic pairs. Since the count can be large, return it modulo 10^9 + 7.

Example 1

Input: nums = [2,3,2]
Output: 4
Explanation: The pairs are ([0,1,1],[2,2,1]), ([0,1,2],[2,2,0]), ([0,2,2],[2,1,0]) and ([1,2,2],[1,1,0]).

Example 2

Input: nums = [5,5,5,5]
Output: 126

Example 3

Input: nums = [1]
Output: 2
Explanation: Either arr1 = [0] and arr2 = [1], or arr1 = [1] and arr2 = [0].

Constraints

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

Hints for Find the Count of Monotonic Pairs I

1. Hint 1

   Once arr1 is fixed, arr2 is forced (arr2[i] = nums[i] - arr1[i]), so count the valid choices of arr1 alone.

2. Hint 2

   Let dp[i][v] be the number of valid prefixes ending with arr1[i] = v. Write down which previous values u = arr1[i - 1] are allowed: u <= v and nums[i - 1] - u >= nums[i] - v.

3. Hint 3

   Both conditions say u <= v - max(0, nums[i] - nums[i - 1]) (and u <= nums[i - 1]), so dp[i][v] is a prefix sum of dp[i - 1].

How to solve Find the Count of Monotonic Pairs I

Choosing arr1 decides arr2, so the task is to count non-decreasing arrays arr1 with 0 <= arr1[i] <= nums[i] whose complement nums[i] - arr1[i] is non-increasing. A DP over the value of arr1[i] counts them, and the allowed previous values always form a prefix, so each state is one prefix-sum lookup.

Approach

1. Start with dp[v] = 1 for every v in 0..nums[0].
2. For each next index i, let d = max(0, nums[i] - nums[i - 1]) and build prefix sums pre of the current dp.
3. For each v in 0..nums[i], the previous value u may be anything up to min(v - d, nums[i - 1]); set ndp[v] = pre[that bound], or 0 when v - d < 0.
4. After the last index, the answer is the sum of dp modulo 10^9 + 7.

Why it works

arr1 non-decreasing means u <= v. arr2 non-increasing means nums[i - 1] - u >= nums[i] - v, i.e. u <= v - (nums[i] - nums[i - 1]). When nums[i] <= nums[i - 1] the second bound is weaker than the first, so the binding bound is v - max(0, nums[i] - nums[i - 1]) — always a prefix of the previous states, which is what makes the prefix sum exact.

Complexity

• Time — O(n · M)
• Space — O(M)

Pitfalls

• arr1 and arr2 are non-negative, so v only ranges over 0..nums[i]; the bound u <= nums[i - 1] matters when v - d exceeds the previous range.
• Reduce the prefix sums modulo 10^9 + 7 as you go — adding up to 51 counts near the modulus overflows a 32-bit integer.

Reference solution

Python

from typing import List

def countOfPairs(nums: List[int]) -> int:
    MOD = 10**9 + 7
    dp = [1] * (nums[0] + 1)
    for i in range(1, len(nums)):
        d = max(0, nums[i] - nums[i - 1])
        pre = []
        s = 0
        for x in dp:
            s = (s + x) % MOD
            pre.append(s)
        ndp = [0] * (nums[i] + 1)
        for v in range(nums[i] + 1):
            top = min(v - d, nums[i - 1])
            if top >= 0:
                ndp[v] = pre[top]
        dp = ndp
    return sum(dp) % MOD

Java

public static int countOfPairs(int[] nums) {
    final long MOD = 1000000007L;
    long[] dp = new long[nums[0] + 1];
    Arrays.fill(dp, 1L);
    for (int i = 1; i < nums.length; i++) {
        int d = Math.max(0, nums[i] - nums[i - 1]);
        long[] pre = new long[dp.length];
        long s = 0;
        for (int u = 0; u < dp.length; u++) { s = (s + dp[u]) % MOD; pre[u] = s; }
        long[] nd = new long[nums[i] + 1];
        for (int v = 0; v <= nums[i]; v++) {
            int top = Math.min(v - d, nums[i - 1]);
            nd[v] = top >= 0 ? pre[top] : 0;
        }
        dp = nd;
    }
    long total = 0;
    for (long x : dp) total = (total + x) % MOD;
    return (int) total;
}

C++

int countOfPairs(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    vector<long long> dp(nums[0] + 1, 1);
    for (size_t i = 1; i < nums.size(); i++) {
        int d = max(0, nums[i] - nums[i - 1]);
        vector<long long> pre(dp.size());
        long long s = 0;
        for (size_t u = 0; u < dp.size(); u++) { s = (s + dp[u]) % MOD; pre[u] = s; }
        vector<long long> nd(nums[i] + 1, 0);
        for (int v = 0; v <= nums[i]; v++) {
            int top = min(v - d, nums[i - 1]);
            if (top >= 0) nd[v] = pre[top];
        }
        dp = nd;
    }
    long long total = 0;
    for (long long x : dp) total = (total + x) % MOD;
    return (int) total;
}

JavaScript

var countOfPairs = function(nums) {
    var MOD = 1000000007;
    var dp = [];
    for (var v = 0; v <= nums[0]; v++) dp.push(1);
    for (var i = 1; i < nums.length; i++) {
        var d = Math.max(0, nums[i] - nums[i - 1]);
        var pre = [], s = 0;
        for (var u = 0; u < dp.length; u++) { s = (s + dp[u]) % MOD; pre.push(s); }
        var nd = [];
        for (var w = 0; w <= nums[i]; w++) {
            var top = Math.min(w - d, nums[i - 1]);
            nd.push(top >= 0 ? pre[top] : 0);
        }
        dp = nd;
    }
    var total = 0;
    for (var t = 0; t < dp.length; t++) total = (total + dp[t]) % MOD;
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard