Find the Count of Monotonic Pairs I

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 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13



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

1
2
3
4



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

Output: 126

Constraints

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

Solution

Method 1 – Dynamic Programming with Prefix Sums

Intuition

For each index, we can split nums[i] into arr1[i] and arr2[i] such that arr1 is non-decreasing and arr2 is non-increasing, and arr1[i] + arr2[i] = nums[i]. The number of ways to do this can be computed using DP, where we keep track of the last value of arr1 and the last value of arr2.

Approach

Let dp[i][a] be the number of ways to fill arr1[0..i] where arr1[i] = a and arr1 is non-decreasing so far.
For each position, for each possible value of arr1[i], sum over all valid arr1[i-1] <= arr1[i].
For each arr1, arr2[i] = nums[i] - arr1[i]. arr2 must be non-increasing, so arr2[i] <= arr2[i-1].
Use prefix sums to speed up the DP transitions.
The answer is the sum over all valid dp[n-1][a].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    int countMonotonicPairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size(), mx = *max_element(nums.begin(), nums.end());
        vector<vector<int>> dp(n, vector<int>(mx+1, 0));
        for (int a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
        for (int i = 1; i < n; ++i) {
            vector<int> pre(mx+2, 0);
            for (int a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
            for (int a = 0; a <= nums[i]; ++a) {
                int b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                if (i == 1 || b <= nums[i-1] - a) {
                    dp[i][a] = pre[a+1];
                }
            }
        }
        int ans = 0;
        for (int a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % MOD;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func countMonotonicPairs(nums []int) int {
    MOD := int(1e9 + 7)
    n := len(nums)
    mx := 0
    for _, v := range nums {
        if v > mx { mx = v }
    }
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, mx+1)
    }
    for a := 0; a <= nums[0]; a++ {
        dp[0][a] = 1
    }
    for i := 1; i < n; i++ {
        pre := make([]int, mx+2)
        for a := 0; a <= nums[i-1]; a++ {
            pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
        }
        for a := 0; a <= nums[i]; a++ {
            b := nums[i] - a
            if b < 0 || b > mx { continue }
            dp[i][a] = pre[a+1]
        }
    }
    ans := 0
    for a := 0; a <= nums[n-1]; a++ {
        ans = (ans + dp[n-1][a]) % MOD
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    public int countMonotonicPairs(int[] nums) {
        int MOD = 1_000_000_007, n = nums.length, mx = 0;
        for (int v : nums) mx = Math.max(mx, v);
        int[][] dp = new int[n][mx+1];
        for (int a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
        for (int i = 1; i < n; ++i) {
            int[] pre = new int[mx+2];
            for (int a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
            for (int a = 0; a <= nums[i]; ++a) {
                int b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                dp[i][a] = pre[a+1];
            }
        }
        int ans = 0;
        for (int a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % MOD;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    fun countMonotonicPairs(nums: IntArray): Int {
        val MOD = 1_000_000_007
        val n = nums.size
        val mx = nums.maxOrNull() ?: 0
        val dp = Array(n) { IntArray(mx+1) }
        for (a in 0..nums[0]) dp[0][a] = 1
        for (i in 1 until n) {
            val pre = IntArray(mx+2)
            for (a in 0..nums[i-1]) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
            for (a in 0..nums[i]) {
                val b = nums[i] - a
                if (b < 0 || b > mx) continue
                dp[i][a] = pre[a+1]
            }
        }
        var ans = 0
        for (a in 0..nums[n-1]) ans = (ans + dp[n-1][a]) % MOD
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def countMonotonicPairs(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        mx = max(nums)
        dp = [[0] * (mx+1) for _ in range(n)]
        for a in range(nums[0]+1):
            dp[0][a] = 1
        for i in range(1, n):
            pre = [0] * (mx+2)
            for a in range(nums[i-1]+1):
                pre[a+1] = (pre[a] + dp[i-1][a]) % MOD
            for a in range(nums[i]+1):
                b = nums[i] - a
                if b < 0 or b > mx:
                    continue
                dp[i][a] = pre[a+1]
        return sum(dp[n-1][a] for a in range(nums[n-1]+1)) % MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


impl Solution {
    pub fn count_monotonic_pairs(nums: Vec<i32>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = nums.len();
        let mx = *nums.iter().max().unwrap();
        let mx = mx as usize;
        let mut dp = vec![vec![0; mx+1]; n];
        for a in 0..=nums[0] as usize {
            dp[0][a] = 1;
        }
        for i in 1..n {
            let mut pre = vec![0; mx+2];
            for a in 0..=nums[i-1] as usize {
                pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
            }
            for a in 0..=nums[i] as usize {
                let b = nums[i] as isize - a as isize;
                if b < 0 || b > mx as isize { continue; }
                dp[i][a] = pre[a+1];
            }
        }
        let mut ans = 0;
        for a in 0..=nums[n-1] as usize {
            ans = (ans + dp[n-1][a]) % MOD;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    countMonotonicPairs(nums: number[]): number {
        const MOD = 1e9 + 7, n = nums.length, mx = Math.max(...nums);
        const dp: number[][] = Array.from({length: n}, () => Array(mx+1).fill(0));
        for (let a = 0; a <= nums[0]; ++a) dp[0][a] = 1;
        for (let i = 1; i < n; ++i) {
            const pre = Array(mx+2).fill(0);
            for (let a = 0; a <= nums[i-1]; ++a) pre[a+1] = (pre[a] + dp[i-1][a]) % MOD;
            for (let a = 0; a <= nums[i]; ++a) {
                const b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                dp[i][a] = pre[a+1];
            }
        }
        let ans = 0;
        for (let a = 0; a <= nums[n-1]; ++a) ans = (ans + dp[n-1][a]) % MOD;
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n * m), where n is the length of nums and m is the max value in nums, due to DP and prefix sums.
🧺 Space complexity: O(n * m), for the DP table.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dynamic Programming with Prefix Sums#

Intuition#

Approach#

Code#

Complexity#