Find the Count of Monotonic Pairs II

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] <= 1000

Solution

Method 1 – Dynamic Programming with 2D State

Intuition

We need to count the number of monotonic pairs (arr1, arr2) where arr1 is non-decreasing, arr2 is non-increasing, and arr1[i] + arr2[i] = nums[i]. Unlike part I, here both arr1 and arr2 must be monotonic, so we need to track both the last value of arr1 and arr2 in our DP.

Approach

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

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:
    def countMonotonicPairs(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        mx = max(nums)
        dp = [[[0]*(mx+1) for _ in range(mx+1)] for _ in range(n)]
        for a in range(nums[0]+1):
            b = nums[0] - a
            dp[0][a][b] = 1
        for i in range(1, n):
            for a in range(nums[i]+1):
                b = nums[i] - a
                if b < 0 or b > mx:
                    continue
                for pa in range(a+1):
                    for pb in range(b, mx+1):
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
        ans = 0
        for a in range(nums[-1]+1):
            b = nums[-1] - a
            if 0 <= b <= mx:
                ans = (ans + dp[n-1][a][b]) % 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


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<vector<int>>> dp(n, vector<vector<int>>(mx+1, vector<int>(mx+1, 0)));
        for (int a = 0; a <= nums[0]; ++a) {
            int b = nums[0] - a;
            dp[0][a][b] = 1;
        }
        for (int i = 1; i < n; ++i) {
            for (int a = 0; a <= nums[i]; ++a) {
                int b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                for (int pa = 0; pa <= a; ++pa) {
                    for (int pb = b; pb <= mx; ++pb) {
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
                    }
                }
            }
        }
        int ans = 0;
        for (int a = 0; a <= nums[n-1]; ++a) {
            int b = nums[n-1] - a;
            if (b < 0 || b > mx) continue;
            ans = (ans + dp[n-1][a][b]) % 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


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][mx+1];
        for (int a = 0; a <= nums[0]; ++a) {
            int b = nums[0] - a;
            dp[0][a][b] = 1;
        }
        for (int i = 1; i < n; ++i) {
            for (int a = 0; a <= nums[i]; ++a) {
                int b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                for (int pa = 0; pa <= a; ++pa) {
                    for (int pb = b; pb <= mx; ++pb) {
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
                    }
                }
            }
        }
        int ans = 0;
        for (int a = 0; a <= nums[n-1]; ++a) {
            int b = nums[n-1] - a;
            if (b < 0 || b > mx) continue;
            ans = (ans + dp[n-1][a][b]) % 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


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) { Array(mx+1) { IntArray(mx+1) } }
        for (a in 0..nums[0]) {
            val b = nums[0] - a
            dp[0][a][b] = 1
        }
        for (i in 1 until n) {
            for (a in 0..nums[i]) {
                val b = nums[i] - a
                if (b < 0 || b > mx) continue
                for (pa in 0..a) {
                    for (pb in b..mx) {
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
                    }
                }
            }
        }
        var ans = 0
        for (a in 0..nums[n-1]) {
            val b = nums[n-1] - a
            if (b < 0 || b > mx) continue
            ans = (ans + dp[n-1][a][b]) % 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
32
33
34
35
36
37


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 j := range dp[i] {
            dp[i][j] = make([]int, mx+1)
        }
    }
    for a := 0; a <= nums[0]; a++ {
        b := nums[0] - a
        dp[0][a][b] = 1
    }
    for i := 1; i < n; i++ {
        for a := 0; a <= nums[i]; a++ {
            b := nums[i] - a
            if b < 0 || b > mx { continue }
            for pa := 0; pa <= a; pa++ {
                for pb := b; pb <= mx; pb++ {
                    dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD
                }
            }
        }
    }
    ans := 0
    for a := 0; a <= nums[n-1]; a++ {
        b := nums[n-1] - a
        if b < 0 || b > mx { continue }
        ans = (ans + dp[n-1][a][b]) % 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


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() as usize;
        let mut dp = vec![vec![vec![0; mx+1]; mx+1]; n];
        for a in 0..=nums[0] as usize {
            let b = nums[0] as usize - a;
            dp[0][a][b] = 1;
        }
        for i in 1..n {
            for a in 0..=nums[i] as usize {
                let b = nums[i] as usize - a;
                if b > mx { continue; }
                for pa in 0..=a {
                    for pb in b..=mx {
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
                    }
                }
            }
        }
        let mut ans = 0;
        for a in 0..=nums[n-1] as usize {
            let b = nums[n-1] as usize - a;
            if b > mx { continue; }
            ans = (ans + dp[n-1][a][b]) % MOD;
        }
        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


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.from({length: mx+1}, () => Array(mx+1).fill(0)));
        for (let a = 0; a <= nums[0]; ++a) {
            const b = nums[0] - a;
            dp[0][a][b] = 1;
        }
        for (let i = 1; i < n; ++i) {
            for (let a = 0; a <= nums[i]; ++a) {
                const b = nums[i] - a;
                if (b < 0 || b > mx) continue;
                for (let pa = 0; pa <= a; ++pa) {
                    for (let pb = b; pb <= mx; ++pb) {
                        dp[i][a][b] = (dp[i][a][b] + dp[i-1][pa][pb]) % MOD;
                    }
                }
            }
        }
        let ans = 0;
        for (let a = 0; a <= nums[n-1]; ++a) {
            const b = nums[n-1] - a;
            if (b < 0 || b > mx) continue;
            ans = (ans + dp[n-1][a][b]) % MOD;
        }
        return ans;
    }
}

Complexity

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

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Dynamic Programming with 2D State#

Intuition#

Approach#

Code#

Complexity#