3251. Find the Count of Monotonic Pairs II

Problem Link

Description

---

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

Solution

---

Python3

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        N = len(nums)
        M = 10 ** 9 + 7
        dp = [[0] * 1001 for _ in range(N)] # dp[index][amount]
 
        # curr >= prev && (nums[i] - curr) <= (nums[i-1] - prev)
        # prev <= curr && prev <= curr - nums[i] + nums[i - 1]
        # simplify => prev <= min(curr, curr - nums[i] + nums[i - 1])
        # so, prev <= min(curr, curr - nums[i] + nums[i - 1])
        # and when prev increases by 1, prev + 1 <= min(curr + 1, curr + 1 - nums[i] + nums[i - 1])
        # and it can be seen that the difference is only one, hence can use prefix sum to compute that
 
        for j in range(nums[0] + 1):
            dp[0][j] = 1
 
        for i in range(1, N):
            ways = 0
            prev = 0
 
            for curr in range(nums[i] + 1):
                if prev <= min(curr, curr - nums[i] + nums[i - 1]):
                    ways += dp[i - 1][prev]
                    ways %= M
                    prev += 1
            
                dp[i][curr] = ways
        
        res = 0
        for curr in range(1001):
            res += dp[N - 1][curr]
            res %= M
 
        return res

C++

class Solution {
public:
    int MOD = 1e9 + 7;
 
    int countOfPairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr1(n);
        vector<int> arr2(n);
        vector<vector<int>> dp(n, vector<int>(1001, 0));
        for (int j = 0; j <= nums[0]; j++)
            dp[0][j] = 1;
        for (int i = 1; i < n; i++){
            int ways = 0;
            int k = 0;
            for (int j = 0; j <= nums[i]; j++){
                // problem I
                // for (int j = 0; j <= nums[i]; j++){
                //     int ways = 0;
                //     for (int k = 0; k <= 50; k++){
                //         if (k <= j && nums[i - 1] - k >= nums[i] - j)
                //             ways = (ways + dp[i - 1][k]) % MOD;
                //     }
                //     dp[i][j] = ways;
                // }
                // problem II
                if (k <= min(j, j - (nums[i] - nums[i - 1]))){
                    ways = (ways + dp[i - 1][k]) % MOD;
                    k++;
                }
            dp[i][j] = ways;
            }
        }
        int res = 0;
        for (int i = 0; i <= 1000; i++)
            res = (res + dp[n - 1][i]) % MOD;
        return res;
    }
};