Skip to content

3250. Find the Count of Monotonic Pairs I

SourceWeekly Contest 410 Q3DifficultyHardRating1897

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

Solutions

Solution 1: Dynamic Programming + Prefix Sum Optimization

Thinking

Split \(\textit{nums}[i]\) into \(\textit{arr1}[i]+\textit{arr2}[i]\) with \(\textit{arr1}\) non-decreasing and \(\textit{arr2}\) non-increasing. \(n\le 2000\) and \(\textit{nums}[i]\le 50\), so enumerating splits is exponential. The state is “up to \(i\) with \(\textit{arr1}[i]=j\)”.

Monotonicity of \(\textit{arr1}\) needs a previous \(j'\le j\); of \(\textit{arr2}\), \(j'\le j+\textit{nums}[i-1]-\textit{nums}[i]\). The feasible \(j'\) form a prefix, so a prefix sum of \(f[i-1]\) transfers in \(O(1)\). The answer is the sum of the last row.

We define \(f[i][j]\) to represent the number of monotonic array pairs for the subarray \([0, \ldots, i]\) where \(\textit{arr1}[i] = j\). Initially, \(f[i][j] = 0\), and the answer is \(\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]\).

When \(i = 0\), we have \(f[0][j] = 1\) for \(0 \leq j \leq \textit{nums}[0]\).

When \(i > 0\), we can calculate \(f[i][j]\) based on \(f[i-1][j']\). Since \(\textit{arr1}\) is non-decreasing, \(j' \leq j\). Additionally, since \(\textit{arr2}\) is non-increasing, \(\textit{nums}[i] - j \leq \textit{nums}[i - 1] - j'\). Thus, \(j' \leq \min(j, j + \textit{nums}[i - 1] - \textit{nums}[i])\).

The answer is \(\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]\).

The time complexity is \(O(nm)\), and the space complexity is \(O(nm)\), where \(n\) represents the length of the array \(\textit{nums}\), and \(m\) represents the maximum value in the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 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 countOfPairs(int[] nums) {
        final int mod = (int) 1e9 + 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;
    }
}

 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 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;
    }
};

 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
func countOfPairs(nums []int) (ans int) {
    const mod int = 1e9 + 7
    n := len(nums)
    m := slices.Max(nums)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    for j := 0; j <= nums[0]; j++ {
        f[0][j] = 1
    }
    g := make([]int, m+1)
    for i := 1; i < n; i++ {
        g[0] = f[i-1][0]
        for j := 1; j <= m; j++ {
            g[j] = (g[j-1] + f[i-1][j]) % mod
        }
        for j := 0; j <= nums[i]; j++ {
            k := min(j, j+nums[i-1]-nums[i])
            if k >= 0 {
                f[i][j] = g[k]
            }
        }
    }
    for j := 0; j <= nums[n-1]; j++ {
        ans = (ans + f[n-1][j]) % mod
    }
    return
}

 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
function countOfPairs(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const m = Math.max(...nums);
    const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
    for (let j = 0; j <= nums[0]; j++) {
        f[0][j] = 1;
    }
    const g: number[] = Array(m + 1).fill(0);
    for (let i = 1; i < n; i++) {
        g[0] = f[i - 1][0];
        for (let j = 1; j <= m; j++) {
            g[j] = (g[j - 1] + f[i - 1][j]) % mod;
        }
        for (let j = 0; j <= nums[i]; j++) {
            const k = Math.min(j, j + nums[i - 1] - nums[i]);
            if (k >= 0) {
                f[i][j] = g[k];
            }
        }
    }
    let ans = 0;
    for (let j = 0; j <= nums[n - 1]; j++) {
        ans = (ans + f[n - 1][j]) % mod;
    }
    return ans;
}

Comments